Comparison of the Network Time Protocol and Digital Time Service Editor's Note This document includes transcripts of an exchange of messages between Dave Mills of UDel, Dennis Ferguson of UToronto, Joe Comuzzi of DEC and Mike Soha of DEC. The issue under discussion is a comparison and evaluation of the Network Time Protocol (NTP) and the Digital Time Service (DTS). It is important to point out that these messages are informal, sometimes opinionated and may contain errors of judgement and technical detail. Some points of confusion and misstatement in the initial exchanges are clarified as the discussion moves on. The messages have been lightly edited to remove nonrelevant asides and repetitive material, as well as to unify format style. This document is provided for informal, collaborative use in research only and should not be quoted or cited in a professional publication. David L. Mills Electrical Engineering Department University of Delaware 1 September 1990 ------------------------------------------------------------------------ Draft document distributed to the NTP engineering group on 12 February 1990: A Comparison of the Network Time Protocol and Digital Time Service David L. Mills Electrical Engineering Department University of Delaware 1. Introduction The Digital Time Service (DTS) for the Digital Network Architecture (DECnet) is intended to synchronize time in computer networks ranging in size from local to wide-area. As such it is intended to provide service comparable to the Network Time Protocol (NTP) for the Internet architecture. This memorandum compares the architectures, functions and design issues of NTP and DTS with respect to correctness, stability, accuracy and reliability. It is based on information available in the various RFCs [MIL89], [MIL90b], journal articles [MIL90a], [MIL90b] and other sources [MIL90c] for NTP and on the DTS functional specification [DEC89]. In this memorandum the stability of a clock is how well it can maintain a constant frequency, the accuracy is how well its frequency and time compare with national standards and the precision is how precisely these quantities can be resolved within a particular timekeeping system. The offset of two clocks is the time difference between them, while the skew is the frequency difference (first derivative of offset with time). Real clocks exhibit some variation in skew (second derivative of offset with time), which is called drift. The correctness of a timekeeping system is the degree to which it indicates valid UTC according to some criteria, while its reliability is the fraction of the time it can be kept operating and connected in the network. Local clocks are maintained at designated time servers, which are timekeeping systems belonging to a synchronization subnet in which each server measures the offsets between its local clock and the clocks of other servers in the subnet. In this memorandum to synchronize frequency means to adjust the clocks in the subnet to run at the same frequency, to synchronize time means to set them to agree at a particular epoch with respect to Coordinated Universal Time (UTC), as provided by national standards, and to synchronize clocks means to synchronize them in both frequency and time. The goal of a distributed timekeeping service such as NTP and DTS is to synchronize the clocks in all participating servers and clients so that all are correct, indicate the same time relative to UTC, and maintain specified measures of stability, accuracy and reliability. By international agreement the primary frequency reference for our civilization is the atomic oscillator. The standard second is determined as a specified number of atomic cycles, the standard day as 86,400 standard seconds and the standard (Julian) year as 365.25 standard days. In order to maintain the nominal solar year, the Gregorian calendar mandates the insertion of leap days, which in the absence of political upheaval can be determined far in advance. In order to maintain the nominal solar day, leap seconds must be inserted at times which cannot be reliably determined in advance. The basis of civil time is the UTC clock, which first ticked at 0h on 1 January 1972. Without knowledge of prior leap seconds, an event determined on the UTC timescale can appear some 15 seconds late on the Julian timescale. Both the NTP and DTS timescales are based on the UTC timescale and are intended to run at atomic frequency with leap seconds inserted at times decreed by international agreement; however, they are each calibrated in different increments starting from different historic dates. While they both are intended to thrive in large, undisciplined network systems, they differ considerably in their statistical models, algorithms and service metrics. In following sections the similarities and differences are discussed at length, along with implications bearing on correctness, stability, accuracy and reliability. 2. Basic Principles and Functionality Both NTP and DTS are designed for use in proliferated computer networks with possibly many embedded local nets interconnected by routers, gateways and bridges and involving both broadcast and point-to-point transmission media. This section summarizes the architecture and service objectives of NTP and DTS in turn. 2.1. The Network Time Protocol The NTP synchronization subnet consists of a tree-structured graph with nodes representing time servers and edges representing the transmission paths between them. The root nodes of the tree are represented by designated primary servers which synchronize to a radio broadcast or calibrated atomic clock. The remaining nodes are designated secondary servers which synchronize to other servers, both primary and secondary. The number of subnet hops between a particular server and a primary server determines the stratum level of that server. All servers, except possibly those at the leaves of the tree, have identical functionality and can operate simultaneously as clients of the next lower stratum level and servers for the next higher one. Servers, both primary and secondary, typically run NTP with several other servers at the same or lower stratum levels; however, a selection algorithm attempts to select the most accurate and reliable server or set of servers from which to actually synchronize the local clock. The selection algorithm, described in more detail later in this document, uses a maximum-likelihood clustering algorithm to determine the best from among a number of possible servers. The synchronization subnet itself is automatically constructed from among the available paths using the distributed Bellman-Ford routing algorithm [BER87], in which the distance metric is modified hop count. NTP operates in various modes in order to improve efficiency on local wires with many clients. These support operation in conventional RPC client/server modes, as well as symmetric and multicast modes. The symmetric modes provide a flexible backup function in which the direction of time synchronization between a pair of servers can reverse due to loss of reachability or quality of service along one path or another in the synchronization subnet. The multicast mode is designed to provide time to personal workstations where the full accuracy of the other modes is not required. The NTP specification includes no architected procedures for servers to obtain addresses of other servers other than by configuration files and public bulletin boards. While servers passively respond to requests from other servers, they must be configured in order to actively probe other servers. Servers configured as active poll other servers continuously, while servers configured as passive poll only when polled by another server. There are no provisions in the present protocol to dynamically activate some servers should other servers fail. In response to stated needs for security features, NTP includes an optional cryptographic authentication mechanism. NTP also includes an optional comprehensive remote monitoring mechanism found necessary for the detection and repair of various problems in server and network configuration and operation. It is anticipated that, when generic features capable of these functions have been developed and deployed in the Internet, the NTP authentication and monitoring mechanisms may be withdrawn. 2.2. The Digital Time Service In DTS a synchronization subnet consists of a structured graph with nodes consisting of clerks, servers, couriers and time providers. With respect to the NTP nomenclature, a time provider is a primary server, a courier is a secondary server intended to import time from one or more distant primary servers for local redistribution and a server is intended to provide time for possibly many end nodes or clerks. Time providers, servers and couriers are evidently generic, in that all perform similar functions and have similar or identical internal structure. The intent is that time providers can be set from radios, telephone calls to NIST [NBS88] or even manually. As in NTP, DTS clients and servers periodically request the time from other servers, although the subnet has only a limited ability to reconfigure in the event of failure. The selection algorithm used in DTS, which is based on the work presented in Marzullo's dissertation and reported in [MAR85], will be discussed in detail later in this document. On local nets DTS servers multicast to each other in order to construct lists of servers available on the local wire. Clerks multicast requests for these lists, which are returned in monocast mode similar to ARP in the Internet. Couriers consult the network directory system to find global time providers. For local-net operation more than one server can be configured to operate as a courier, but only one will actually operate as a courier at a time. There does not appear to be a multicast function in which a personal workstation could obtain time simply by listening on the local wire without first obtaining a list of local servers. In the DTS model the directory, authentication and management functions are provided by other layers, entities and protocols in the DECnet architecture. As evident from other documents in the DECnet specification suite, these functions are evidently highly developed and integrated in the architecture and presumably provide equivalent functionality as the NTP authentication and monitoring mechanisms. 3. Statistical Models and Data Representation Perhaps the widest departure between the NTP and DTS philosophies is the basic underlying statistical model. NTP is based on maximum-likelihood principles and statistical mechanics, where errors are expressed in terms of expectations. DTS is based on provable assertions about the correctness of a set of mutually suspicious clocks, where errors are expressed as a set of computable bounds on maximum time and frequency offsets. This section explores these models and how they affect the quality of service. 3.1. Statistical Models The conventional analytical model for real synchronized clocks [ALL74], [MIT80] consists of a set of oscillators connected by transmission paths. The oscillators are characterized by a set of random variables that describe their intrinsic time and frequency offsets relative to a reference timescale. In this analysis the time and frequency of an oscillator cannot be known exactly and must be described using random variables with assumed or derived probability density functions. It is possible to quantify absolute upper and lower limits of accuracy only with respect to the these functions. In conventional analysis the transmission paths between the clocks are modelled as stochastic delays, with assumed distributions, usually of exponential type. These paths are used to exchange timing information and adjust the time and frequency offsets of each oscillator. The behavior of individual clocks, both in accuracy and stability, can then be characterized using standard engineering tools, such as the theory of phase-locked loops familiar to communications engineers [LIN80], [SMI86]. In the model used by DTS and several others in the literature (see MIL90b]) a number of assumptions are made, explicitly or implicitly, about the shape of the probability density functions describing the inherent accuracy and stability of clocks, as well as the delays on the transmission paths connecting them. DTS assumes the reading error (offset relative to UTC) of a clock has a computable bound. In addition, DTS assumes the frequency error (called drift in the DTS functional specification) is bounded by an implementation constant. A correct clock never strays outside these bounds, which are computed from the inherent characteristics of the clock, the inherited characteristics of its selected synchronization source, the measured propagation delay and the accumulated error since last updated. If it is assumed that real clocks and transmission paths can be modelled reliably in this fashion, then the DTS algorithm can maintain a system of correct clocks. The philosophy inherent in the NTP algorithms is to consider all possible information available in the stochastic model and measured statistics to arrive at a probabilistic conclusion. The time delivered by an NTP subnet is intended to be the most likely measurement in a probabilistic system in which all measurements have been weighted toward the most likely outcome. However, there is no guarantee that all clocks in the system are valid in the sense of provable correctness. No attempt is made to determine correctness other than on a statistical basis. On the other hand, DTS starts with a set of assumptions on the bounds of error and growth of error bounds with time. The clock selection algorithm is based on an intersection operation which preserves correctness according to these assumptions. As long as the underlying probability distributions can be bounded absolutely, DTS will deliver provably correct time, if at all. But, real distributions seldom behave this way, especially in the Internet, where the distributions can have surprisingly long tails. Thus, there will almost always exist a tail in the distribution which can be truncated only at the expense of some error. In other words, the DTS assumptions must be considered valid only in the context of the probability distributions actually observed. In summary, NTP attempts to deliver the best estimate of time and frequency with presumably the lowest estimated error, but can not guarantee the correctness of the indication relative to an arbitrary set of rigid assumptions. DTS attempts to deliver correct time according to stated assumptions, but correctness can be guaranteed only with respect to these assumptions and these assumptions can be guaranteed only on a probabilistic basis. 3.2. Maximum Likelihood Estimation It is possible to obtain various measures of expected error when processing timekeeping data and use these measures to establish preference in the various estimation algorithms. Called maximum- likelihood estimation, these techniques are widely used in signal processing and communication systems. For instance, experiments show [MIL90b] that, in a list of delay/offset measurements ordered by roundtrip delay, the most accurate offsets are usually associated with the lower delays. When selecting the best offset sample from a single clock or when selecting the best set of clocks in an ensemble, NTP gives the lower-delay samples greater weight in the filtering, selection and combining procedures. Now consider the DTS selection algorithm, which is due to Marzullo [MAR85]. The following diagram shows two scenarios (1) and (2) involving three clocks A, B and C. Each of the dashed lines represents the interval of time offsets considered correct for that clock. As suggested in [MAR85], the probability of a particular clock reading can be assumed independent and uniformly distributed over the entire interval. A +--------------------------+ A +-+ B +--------------------------+ B +-+ C +-+ C +-+ Result +-+ Result +-+ (1) (2) According to the algorithm, the outcome is determined in both cases by the intersection of the three intervals. However, once the intersection has been formed, all probabilistic information of antecedent distributions is lost. Put another way, the probability of the joint event consisting of the intersection of all three intervals is far lower in (1) than in (2). In NTP this information has proved highly useful in mitigating clock selection; however, the information is lost in DTS. 3.3. Representation of Timestamp Data Both NTP and DTS exist to provide timestamps to some specified accuracy and precision. NTP represents time as a 64-bit quantity in seconds and fractions, with 32 bits as integral seconds and 32 bits as the fraction of a second. This provides resolution to about 200 picoseconds and rollover ambiguity of about 136 years. The origin of the timescale and its correspondence with UTC, atomic time and Julian days is documented in [MIL90c]. DTS represents time to a precision of 100 nanoseconds, although there appears to be no specified maximum value. The origin of the present 136-year NTP time cycle is specified as the first instant of the tropical year that began this century, which is an astronomically verifiable epoch. The origin of the DTS timescale appears to be implementation of the papal bull establishing the Gregorian calendar in 1582, although this instant is verifiable only by historic record. However, UTC did not exist prior to 1972 and the Gregorian calendar did not achieve widespread use until the early years of the twentieth century. While not specified, presumably DTS reckons the years, leap years and Julian days of the conventional calendar as described in the NTP specification [MIL89] and further elaborated in [MIL90c]. In retrospect, it might have been better if both NTP and DTS had adopted Modified Julian Day (MJD) numbering directly and avoided tropical centuries and papal bulls altogether. With respect to applications involving precision time data, such as national standards laboratories, resolutions less than the 100 nanoseconds provided by DTS are required. Present timekeeping systems for space science and navigation can maintain time to better than 30 nanoseconds, while range data over interplanetary distances can be determined to less than a nanosecond. While an ordinary application running on an ordinary computer could not reasonably be expected to expect or render precise timestamps anywhere near the 200-picosecond limit of an NTP timestamp, there are many applications where a precision timestamp could be rendered by some other means and propagated via a computer and network to some other place for processing. One such application could well be synchronizing navigation systems like LORAN-C, where the timestamps would be obtained directly from station timekeeping equipment. 3.4. Time Zones and Leap Seconds NTP specifically and intentionally has no provisions anywhere in the protocol to specify time zones or zone names. The service is designed to deliver UTC seconds and Julian days without respect to geographic position, political boundary or local custom. Conversion of NTP timestamp data to system format is expected to occur at the presentation layer; however, provisions are made to supply leap-second information to the presentation layer so that network time in the vicinity of leap seconds can be properly coordinated. DTS includes provision for time zones and presumably summer/winter adjustments in the form of a numerical time offset from UTC and arbitrary character-string label; however, it is not obvious how to distribute and activate this information in a coordinated manner. NTP and DTS differ somewhat in the treatment of leap seconds. In DTS the normal growth in error bounds in the absence of corrections will eventually cause the bounds to include the new timescale and adjust gradually as in normal operation. Recognizing that this can take a long time, DTS includes special provisions that expand the error bounds at such times that leap seconds are expected to occur, which can shorten the period for convergence significantly. However, until the correction is determined and during the convergence interval the accuracy of the local clock with respect to other network clocks may be considerably degraded. The accuracy and stability expectations of NTP preclude this approach. In NTP the incidence of leap seconds is assumed available in advance at all primary servers and distributed automatically throughout the remainder of the synchronization subnet as part of normal protocol operations. Thus, every server and client in the subnet is aware at the instant the leap second is to take affect, and steps the local clock simultaneously with all other servers in the subnet. Thus, the local clock accuracy and stability are preserved before, during and after the leap insertion. 3.5. Determining Time Offset and Roundtrip Delay At first glance it may appear that NTP and DTS have quite different models to determine delay, offset and error budgets. Both involve the exchange of messages between two servers (or a client and a server). Both attempt to measure not only the clock offsets, but the roundtrip delay and, in addition, attempt to estimate the error. The diagrams below, in which time flows downward, illustrate a typical message exchange in each protocol between servers A and B. A B A B | | | | t1 |--------->| t2 t1 |--------->|--- t4 | | | | | | | | | | | | | w | | | | | | | | | t4 |<---------| t3 t8 |<---------|--- | | | | NTP DTS In NTP the roundtrip delay d and clock offset c of server B relative to A is d = (t4-t1) - (t3-t2) c = ((t2-t1) + (t3-t4))/2. This method amounts to a continuously sampled, returnable-time system, which is used in some digital telephone networks [LIN80]. Among its advantages are that both server A and server B can simultaneously calculate the delay and offset knowing only the latest time of arrival and the three preceding timestamps, which in NTP are carried with the message and can also used for authentication purposes. the order and timing of the messages are unimportant and reliable delivery is not required. In DTS server A remembers timestamp t1 (other numbered events shown in the DTS functional specification are not shown in the diagram) and expects server B to return t4, the time of arrival of the request from server A, and w, the time elapsed until the departure of the response to server A. In principle, although NTP is symmetric and DTS is not, the two schemes are computationally equivalent and either can compute delay and offset using similar formulas. Both NTP and DTS have to do a little dance in order to account for timing errors due to the precisions of the local clocks and the frequency offsets (usually minor) over the transaction interval itself. A purist might argue that the expression given above for delay and offset are not strictly accurate unless the probability density functions for the path delays are known, properly convolved and expectations computed, but this applies to both NTP and DTS. The point should be made, however, that correct functioning of DTS requires reliable bounds on measured roundtrip delay, as this enters into the error budget used to construct intervals over which a clock can be considered correct. This is not nearly as important in NTP, since the accuracy and stability of the local clock is largely due to the local clock model, which is described later in this document. 4. Processing Algorithms At the heart of any time synchronization system are the algorithms which process the data received from possibly many servers, filter out noise in the form of outlyers and select the best from among a population of mutually suspicious clocks. Issues of the NTP and DTS data filtering, clock selection and combining algorithms are compared and discussed in following subsections. 4.1. Data Filtering In both the NTP and DTS models a number of offsets are collected from each of possibly many servers. In principle, the accuracy and precision of measurements made between any pair of servers can be improved by selecting or combining a number of sequential samples in various ways. In NTP a comprehensive program of analysis and experiment lasting several years and using many Internet transmission paths involving local nets and wide-area nets resulted in what is called the minimum-filter algorithm [MIL90b]. Reduced to essentials, this algorithm selects from among the last n samples of delay/offset collected from a single server the sample with minimum delay and presents the associated offset as the time offset estimate for that server. This is done separately for each server on a continuous basis at intervals from about one minute to about 17 minutes. As part of this continuing process, an error estimate called the sample dispersion is constructed as the sum of weighted differences of the resulting estimate offset relative to the other n-1 samples considered in the selection. In DTS the same algorithm used to select a cohort set of servers from a population possibly including faulty servers (see next section) is used to filter the samples from a single server. This approach was discarded early in the NTP design experience for two reasons. First, the statistical problem of selecting good samples from a sequence produced by a single server has the very considerable advantage that the underlying probability distribution can be assumed stationary and represented by robust statistics such as produced by nonlinear trimmed- mean filters, median filters and the NTP minimum filter. Second, the problem of selecting good clocks from bad involves a multivariate statistical model characteristic of pattern analysis and classification. It has been the NTP experience that algorithms that work well on one of these two problems usually do not do well on the other. 4.2. Clock Selection and Combining In both NTP and DTS the problem persists that there is often no clear distinction between truechimers and falsetickers, so that "correct" clocks can be deduced only on a probabilistic basis and then only according to arbitrary criteria. It could be argued on the basis of experience, for example, that various kinds of faulty behavior are more likely than others. For instance, it is probable that a faulty clock more likely indicates hot ones, cold zeros or an integral number of seconds, minutes, days or years in error, rather than fractional parts of these quantities. A clock that comes up with no prior hint of correct time has a vanishing probability of coming up anywhere near UTC by simple nature of the measurement space. In NTP, for example, this would amount to guessing the correct 256-ms window in an interval of 136 years. Interesting observations on these points, including the use of an NTP timestamp as a cryptographic one-time pad, can be found in the references. NTP maintains for each server both the total estimated roundtrip delay to the root of the synchronization subnet (synchronizing distance), as well as the sum of the total dispersion to the root of the synchronization subnet (synchronizing dispersion). These quantities are included in the message exchanges and form the basis of the likelihood calculations. Since they always increase from the root, they can be used to calculate accuracy and reliability estimates, as well as to manage the subnet topology to reduce errors and resist destructive timing loops. In NTP the selection algorithm determines one or a number of synchronization candidates based on empirical rules and maximum- likelihood techniques. A combining algorithm determines the local-clock adjustment using a weighted-average procedure in which the weights are determined by offset sample dispersion. The algorithm begins by constructing a list of candidate clocks sorted first by stratum and then by total synchronization dispersion to the root. The list is then pruned from the end to a manageable size and to eliminate very noisy and probably defective clocks. On the assumption that a valid synchronization candidate will always be at the lowest or next from lowest stratum, the list is truncated at the first entry where the number of different strata on the list exceeds two. This particular procedure and choice of parameters have been found to produce reliable synchronization candidates over a wide range of system environments while minimizing the "pulling" effect of high-stratum, high-dispersion servers, especially when a large number of servers are involved. The next step is designed to detect falsetickers or other conditions which might result in gross errors. The pruned and truncated candidate list is re-sorted in the order first by stratum and then by total synchronizing distance to the root; that is, in order of decreasing likelihood. A similar procedure is also used in Marzullo's MM algorithm [MAR85]. Next, each entry is inspected in turn and a weighted error estimate computed relative to the remaining entries on the list. The entry with maximum estimated error is discarded and the process repeats. The procedure terminates when the estimated error of each entry remaining on the list is less than a quantity depending on the intrinsic precisions of the local clocks involved. The NTP selection algorithm is designed to favor those servers near the head (maximum likelihood) of the candidate list, which are at the lowest stratum and lowest delay and presumably can provide the most accurate time. With proper selection of weighting factors, outlyers are discarded from the tail of the list, unless some other entry disagrees significantly with respect to the remaining entries, in which case that entry is discarded first. The offsets of the surviving servers are statistically equivalent, so any of them can be chosen to adjust the local clock. Some implementations [MIL90c] combine them using a weighted-average algorithm similar to that used by national standards laboratories [ALL74], in which the offsets of the servers remaining on the list are weighted by sample dispersion to produce a combined estimate. DTS uses a rather different technique, where the goal emphasized is validated correctness relative to a set of specified criteria. A compact way of expressing this algorithm is the following. Each clock is expressed as an estimate C and an inherent or inherited error E, which defines an interval [C-E,C+E]. A clock is correct if the interval includes UTC and incorrect if not; however, it is not known in advance which is the case. Consider M such intervals with j possibly faulty servers and arrange the lower endpoints on a list by increasing endpoint value. Starting from the beginning of the list, find the first point which is contained in at least M-f intervals. This defines the lower boundary of the correct interval. If no such point is found, increase f by one and try again. A similar procedure is used for the upper limit of the correct interval. The error E used to construct the above intervals is determined both by the intrinsic characteristics of the clock oscillator (precision), the reading delay between the client request and server response and the frequency offset over the interval since the oscillator was last adjusted. Once established by the above algorithm, the correct interval grows with time, possibly engulfing intervals previously considered faulty. The interval between client requests is carefully computed to prevent the correct interval from exceeding a configuration parameter. The fundamental assumption upon which the DTS is founded is Marzullo's proof that a set of M clocks synchronized by the above algorithm, where no more than j clocks are faulty, delivers an interval including UTC. The algorithm is simple, both to express and to implement, and involves only one sorting step instead of two as in NTP. However, consider the following scenario with M = 3, j = 1 and containing three intervals A, B and C: A +--------------------------+ B +----+ C +----+ Result +-----================-----+ Using the algorithm described in the DTS functional specification, both the lower and upper endpoints of interval A are in M-j = 2 intervals, thus the resulting interval is coincident with A. However, there remains the interval marked "=" which contains points not contained in at least two other intervals. The DTS document mentions this interesting fact, but makes a quite reasonable choice to avoid multiple intervals in favor of a single one, even if that does in principle violate the correctness assumptions. The purist would say that a choice has to be made, either the left intersection or the right one, perhaps mitigated by maximum- likelihood principles. This example would seem to violate the fundamental basis on which the proof of correctness of Marzullo's algorithm is based. In fact, quite similar algorithms were once used in predecessors of NTP [MIL85a], [MIL85b], but discarded because they produced inadequate accuracy and stability. One of the problems with algorithms such as this is that normal variations in network path delay cause frequent occasions when one clock or another pops in or out of one correction interval or another, causing the interval to change size and resulting in large phase noise of the local clock. While the phenomenon is much reduced in the present NTP design, some "clockhopping" does occur and is the primary contributor in NTP to clock instability. Another reason these algorithms were abandoned was that incidental error estimates, such as the size of the correct interval, cannot be used either for likelihood estimation or to organize the subnet topology. 5. Local Clocks There are fundamental differences between the NTP and DTS local-clock models. The DTS (and Unix) model assumes the local clock runs at a rate R determined by its integral quartz resonator, which may be manufactured to a tolerance no better than 100 ppm, which corresponds to several seconds per day. A correction is introduced as an offset, which causes a number of fractional seconds to be added or subtracted from the local clock. In order to avoid large discontinuities and insure monotonicity, the rate at which the clock can be adjusted is fixed by an implementation constant e (called tickadjust in the Unix kernel). The local clock thus runs at three rates: R, R+e and R-e, so that the magnitude of correction determines not the magnitude of the rate, but the length of time over which the rate is continued. Once the correction has been completed, the clock reverts to rate R and continues indefinitely at that rate. From the DTS functional specification it appears that the designers expect that corrections be recomputed on the order of one every 15 minutes to once per hour. Early in the evolution of NTP the above model was discarded as the result of experience with sometimes broken servers and always noisy transmission paths. The factor missing in the DTS design is a capability to compensate for frequency errors as well as time errors. The NTP local-clock model includes provisions to estimate the frequency error and automatically adjust the local clock by introducing additional offset corrections on a regular basis. This results in much reduced frequency errors in the order of .01 ppm or a few milliseconds per day in the absence of external corrections. In principal and depending on the inherent stability of the local clock, the interval between corrections can be reduced to the order of hours and even days. However, if some or all of the servers in the synchronization subnet are to incorporate frequency management, the clock adjustment dynamics must be controlled and held to specified tolerances; otherwise, some servers can become unstable and experience wild time and frequency gyrations. In control theory the DTS design is described as a type-I feedback loop, which is unconditionally stable, while the NTP design is described as a type-II loop, which can become unstable under some conditions. This requires specification of the adjustment rate, including the value of e for Unix-style clocks, as well as a specified mechanism to adjust the frequency as required. While this has proved a surmountable problem with NTP daemons for Unix, it has been suggested that appropriately specified functionality be incorporated directly into the design of the kernel timekeeping facility, in which case DTS and possibly other schemes could benefit as well. For the most accurate and precise time and frequency using ordinary hardware components it is necessary to fine-tune the adjustment dynamics to match expected local clock jitter, wander and drift. The NTP model incorporates this functionality using a drift estimate (kurtosis) which dynamically adjusts the loop bandwidth. It is arguable whether diligent pursuit of the highest quality service always justifies the additional complexity, but it is certainly necessary if accuracies in the order of a few milliseconds and stabilities in the order of a few milliseconds per day are required, especially for the primary servers. Since stability of the subnet itself is not critically dependent on this feature, it can be considered optional in the specification and implementation. In point of fact, the local clock model described in the NTP specification is listed as optional in the same spirit as the model described in the DTS functional description. As such, the local clock can in principle be considered implementation specific and not part of the formal specification. However, as demonstrated above, frequency compensation requires the local clock adjustment to be carefully specified and implemented. The NTP mechanism has been carefully analyzed, simulated, implemented and deployed in the Internet, but DTS has not. The unavoidable conclusion is that NTP and DTS implementations cannot safely interoperate in subnets of any size, unless the DTS local clock adjustment mechanism is suitably modified. 5.2. Monotonicity It is an uncontested fact that computer systems can be badly disrupted should apparent time appear to warp (jump) backwards, rather than always tick forward as our universe requires. Both NTP and DTS take explicit precautions to avoid the local clock running backwards or large warps when running forwards. However, both NTP and DTS models recognize that there are some extreme conditions in which it is better to warp backwards or forwards, rather than allow the adjustment procedure to continue for an outrageously long time. The local clock is warped if the correction exceeds an implementation constant, +-128 milliseconds for NTP and ten minutes for DTS. The large difference between the NTP and DTS values is attributed to the accuracy models assumed. For most servers and transmission paths in the Internet a offset spike (following filtering, selection and combining operations) over +-128 milliseconds following filtering, selection and combining operations is so rare as to be almost negligible. For the few exceptions operating in extreme dispersive conditions, such as statistical multiplexors or switched landline/satellite paths, the 128-ms value can be increased by a configuration parameter. The problem with selecting larger values is that the time taken to affect a spike correction can be rather long, during which the clock accuracy specification can be exceeded. Obviously, the same considerations apply in DTS. 5.3. Epoch Determination The DTS functional specification points out an interesting requirement, common to other network management and routing protocols, which require circuit breakers between a set of clocks synchronized to each other but known to be faulty and another set synchronized to each other but known to be correct. The problem is to avoid infection of the set of correct clocks by timestamps from the faulty set. DTS provides this circuit breaker in the form of an epoch number, which is incremented when a new subnet is created. Once the first member of the new subnet has been created, others can be transferred from the faulty to the correct subnet one at a time so that correctness is preserved. In NTP the circuit breaker is provided by the authentication mechanism, which can operate with any of several encryption keys. When a new subnet is created, all that is required is to change the key of a known correct server and then change the keys of other servers one at a time. Eventually all servers are running with the new key and the subnet continues as usual. The same scheme has also been used when testing new implementations and on occasion to isolate known falsetickers which cannot otherwise be partitioned from the Internet. 5.4. Dynamic Polling Intervals In both NTP and DTS servers exchange timekeeping data at regular intervals. In NTP the polling intervals are dynamically adjusted from about one minute to about 17 minutes, depending on sample dispersion and local clock stability. In DTS the intervals are fixed, with lower bounds of two minutes (servers) and 15 minutes (clerks) and upper bounds depending on error tolerance. Relatively frequent polls are necessary both to confirm reachability (for hot standby service), as well as to maintain accuracy within specified limits (DTS) and to maintain optimum subnet stability (NTP). At the present stage of protocol refinement, NTP polling intervals can be expected to be somewhat less than DTP intervals. The reason for this is the emphasis in NTP on the highest attainable accuracy and stability, which requires compensation for frequency errors as well as timing errors. Stability of the closed-loop system without bandwidth control presently requires a maximum polling interval in the order of one minute for those transmission paths actually used to maintain synchronization; however, the polling interval is increased typically to 17 minutes for other paths, which statistically account for more than two-thirds of the total number of paths. However, with the introduction of bandwidth control in the latest NTP implementations, the polling interval can be increased to 17 minutes on all paths, with the expectation of even larger increases at the higher stratum levels. 6. Summary and Conclusions The service objectives of both NTP and DTS are substantially the same: to deliver correct, accurate, stable and reliable time throughout the synchronization subnet. However, as demonstrated in this document, these objectives are not all simultaneously achievable. For instance, in a system of real clocks some may be correct according to an established and trusted criterion (truechimers) and some may not (falsetickers). In the models used by NTP and DTS the distinction between these two groups is made on the basis of different clustering techniques, neither of which is statistically infallible. A succinct way of putting it might be to say that NTP attempts to deliver the most accurate, stable and reliable time according to statistical principles, while DTS attempts to deliver validated time according to correctness principles, but possibly at the expense of accuracy and stability. In both the NTP or DTS models the problem is to determine which subset of possibly many clocks represents the truechimers and which do not. An interesting observation about both NTP and DTS is that neither attempts to assess the relative importance of misses (mislabelling a truechimer as a falseticker) relative to false alarms (mislabelling a falseticker as a truechimer). In signal detection analysis this is established by the likelihood ratio, with high ratios favoring misses over false alarms. In retrospect, it could be said that NTP assumes a somewhat lower likelihood ratio than does DTS. It might be concluded from the discourse in this document that, if the service objective is the highest accuracy and precision, then the protocol of choice is NTP; however, if the objective is correctness, then the protocol of choice is DTS. However, the discussion in Section 4.2 casts some doubt either on this claim, the DTS functional specification or this investigator's interpretation of it. It is certainly true that DTS is "simple" and NTP is "complex," but these are relative terms and the complexity of NTP did not result from accident. That even the complexity of NTP is surmountable is demonstrated by the fact that over 2000 NTP-synchronized servers chime each other in the Internet now. The most serious departure between NTP and DTS, and the reason that subnets incorporating large numbers of either protocol can not interoperate safely without further consideration, is the fact that in NTP it has been found necessary to implement local clock frequency compensation and in DTS it has not. Whether or not the additional rigor in specification and implementation can be justified depends on the expectation of the time-service customers and their applications. Frequency compensation not only provides the capability to survive long server outages while keeping good local time, but is instrumental in reducing timing noise and maintaining the highest accuracy and stability. The widespread deployment of NTP in the Internet seems to confirm that distributed Internet applications can expect that reliable, synchronized time can be maintained to within about two orders of magnitude less than the overall roundtrip delay to the root of the synchronization subnet. For most places in the Internet today that means overall network time can be confidently maintained to a few tens of milliseconds [MIL90a]. While the behavior of large-scale deployment of DTS in internet environments is unknown, it is unlikely that it can provide comparable performance in its present form. With respect to the future refinement of DTS, should this be considered, it is inevitable that the same performance obstacles and implementation choices found by NTP will be found by DTS as well. 7. References [ALL74] Allan, D.W., J.E. Gray and H.E. Machlan. The National Bureau of Standards atomic time scale: generation, stability, accuracy and accessibility. In: Blair, B.E. (Ed.). Time and Frequency Theory and Fundamentals. National Bureau of Standards Monograph 140, U.S. Department of Commerce, 1974, 205-231. [BER87] Bertsekas, D., and R. Gallager. Data Networks. Prentice-Hall, Englewood Cliffs, NJ, 1987. [DIG89] Digital Equipment Corporation. Digital Time Service functional specification, version T1.0.5. Digital Equipment Corporation, December 1989. [LIN80] Lindsay, W.C., and A.V. Kantak. Network synchronization of random signals. IEEE Trans. Communications COM-28, 8 (August 1980), 1260-1266. [MAR85] Marzullo, K., and S. Owicki. Maintaining the time in a distributed system. ACM Operating Systems Review 19, 3 (July 1985), 44-54. [MIL85a] Mills, D.L. Algorithms for synchronizing network clocks. DARPA Network Working Group Report RFC-956, M/A-COM Linkabit, September 1985. [MIL85b] Mills, D.L. Experiments in network clock synchronization. DARPA Network Working Group Report RFC-957, M/A-COM Linkabit, September 1985. [MIL89] Mills, D.L. Network Time Protocol (Version 2) specification and implementation. DARPA Network Working Group Report RFC-1119, University of Delaware, September 1989. [MIL90a] Mills, D.L. On the accuracy and stability of clocks synchronized by the Network Time Protocol in the Internet system. ACM Computer Communication Review 20, 1 (January 1990), 65-75. [MIL90b] Mills, D.L. Internet time synchronization: the Network Time Protocol. IEEE Trans. Communications (to appear). See also: DARPA Network Working Group Report RFC-1129, University of Delawary, October 1989. [MIL90c] Mills, D.L. The NTP Local-Clock Model and Control Algorithms. (unpublished), February 1990 [MIT80] Mitra, D. Network synchronization: analysis of a hybrid of master-slave and mutual synchronization. IEEE Trans. Communications COM-28, 8 (August 1980), 1245-1259. [NBS88] Automated Computer Time Service (ACTS). NBS Research Material 8101, U.S. Department of Commerce, 1988. [SMI86] Smith, J. Modern Communications Circuits. McGraw-Hill, New York, NY, 1986. ------------------------------------------------------------------------ Date: Fri, 16 Mar 90 09:58:35 PST From: comuzzi@took.enet.dec.com To: mills@udel.edu Subject: RE: DTS and NTP revisited ... The Digital Time Service (DTS) for the Digital Network Architecture (DECnet) is intended to synchronize time in computer networks ranging in size from local to wide-area. You seem to be trying to clothe DTS in a propritary cloth. We now refer to DECnet as DECnet/OSI since we've incorporated OSI protocols into the protocol stack. It is our intention to pursue DTS in the OSI standards forums. As such it is intended to provide service comparable to the Network Time Protocol (NTP) for the Internet architecture. While both are clearly addressing the same problem space, DTS and NTP have VERY different goals. I recently spoke to the president of a time provider manufacturer and I liked his jargon, he distinguished between the time-of-day market and the frequency market. The time-of-day market wants to know what time it is, it is not interested in small errors and it doesn't want to pay a lot. The frequency market wants stable frequency sources, needs high stability and is willing to pay. NTP is a solution for the frequency market. DTS is only interested in the time-of-day market. The major cost for these solutions is not the initial capital investment, but the long term management and operation cost. As such DTS has goals of auto-configurability and ease of management which are not present in NTP. ... Local clocks are maintained at designated time servers, which are timekeeping systems belonging to a synchronization subnet in which each server measures the offsets between its local clock and the clocks of other servers in the subnet. In this memorandum to synchronize frequency means to adjust the clocks in the subnet to run at the same frequency, to synchronize time means to set them to agree at a particular epoch with respect to Coordinated Universal Time (UTC), as provided by national standards, and to synchronize clocks means to synchronize them in both frequency and time. The goal of a distributed timekeeping service such as NTP and DTS is to synchronize the clocks in all participating servers and clients so that all are correct, indicate the same time relative to UTC, and maintain specified measures of stability, accuracy and reliability. As stated above, DTS is addressing the time-of-day market hence high frequency stability is an not a goal of DTS. ... Servers, both primary and secondary, typically run NTP with several other servers at the same or lower stratum levels; however, a selection algorithm attempts to select the most accurate and reliable server or set of servers from which to actually synchronize the local clock. The selection algorithm, described in more detail later in this document, uses a maximum-likelihood clustering algorithm to determine the best from among a number of possible servers. The synchronization subnet itself is automatically constructed from among the available paths using the distributed Bellman-Ford routing algorithm [BER87], in which the distance metric is modified hop count. Note that in DTS loops are not a problem, if a system sends out a time an ultimately gets back a derived time, due to the communication delays the derived time will always arrive back with a larger inaccuracy. The only exception to this is the possiblity of a system with a time provider and a lousy clock. Then the derived time's inaccuracy could be smaller if the time was parked in a system with a good clock. But in this case the network clearly has information that the original system has lost. ... The NTP specification includes no architected procedures for servers to obtain addresses of other servers other than by configuration files and public bulletin boards. This is a serious short-coming of NTP and definitely makes it harder to manage. It is unclear to me why you haven't fixed this since it would not seem that difficult to store server names in a namespace. While servers passively respond to requests from other servers, they must be configured in order to actively probe other servers. Servers configured as active poll other servers continuously, while servers configured as passive poll only when polled by another server. There are no provisions in the present protocol to dynamically activate some servers should other servers fail. This is harder to fix and interacts with the spanning tree. Here at least I can see why you didn't make it easier to manage. These problems make NTP a system administrators nightmare, but are consistent with the two different sets of goals. Consistent with DTS goals we've accepted some "clock hopping" in exchange for ease of management. ... In DTS a synchronization subnet consists of a structured graph with nodes consisting of clerks, servers, couriers and time providers. With respect to the NTP nomenclature, a time provider is a primary server, a courier is a secondary server intended to import time from one or more distant primary servers for local redistribution and a server is intended to provide time for possibly many end nodes or clerks. Time providers, servers and couriers are evidently generic, in that all perform similar functions and have similar or identical internal structure. Not only are they generic, they are dynamic. If a time provider system loses its radio signal, it immediately reverts to a server, providing graceful degradation in the presence of failures. ... The intent is that time providers can be set from radios, telephone calls to NIST [NBS88] or even manually. The DTS story is actually even better here, we provide a well defined time provider interface. This can be used to implement a time provider without requiring modification of the protocol portions of the time service. (On Unix systems it uses Unix domain sockets). This greatly eases adding a new time provider, and permits time provider vendors to supply it with their hardware. Note, NTP could (and probably should) do this also. We have already done it. As in NTP, DTS clients and servers periodically request the time from other servers, although the subnet has only a limited ability to reconfigure in the event of failure. I don't understand this statement. Reconfiguration within a LAN is about as complete as one could imagine. The random selection of global servers is robust against any non-partitioning WAN failures. On local nets DTS servers multicast to each other in order to construct lists of servers available on the local wire. Clerks multicast requests for these lists, which are returned in monocast mode similar to ARP in the Internet. Couriers consult the network directory system to find global time providers. For local-net operation more than one server can be configured to operate as a courier, but only one will actually operate as a courier at a time. This is false, I think you're failing to distinguish between couriers and backup couriers. There can be more than one courier per LAN, each will always synchronize with at least one member of the global set. Backup couriers use an election algorithm in the absence of a courier. Only one backup courier will be elected to function as a courier. There does not appear to be a multicast function in which a personal workstation could obtain time simply by listening on the local wire without first obtaining a list of local servers. That is correct, it would violate the principle that a message exchange has to happen in order to correctly assign an inaccuracy. ... Both NTP and DTS exist to provide timestamps to some specified accuracy and precision. NTP represents time as a 64-bit quantity in seconds and fractions, with 32 bits as integral seconds and 32 bits as the fraction of a second. This provides resolution to about 200 picoseconds and rollover ambiguity of about 136 years. The origin of the timescale and its correspondence with UTC, atomic time and Julian days is documented in [MIL90c]. DTS represents time to a precision of 100 nanoseconds, although there appears to be no specified maximum value. The DTS time is a signed 64 bits of 100 nanoseconds since Oct 15, 1582. It will not run out until after the year 30,000 AD. Unlike NTP which will run out in 2036. I, for one, intend to still be alive in 2036! There are two reasons the 100 ns. was chosen: 1) We want to use these timestamps as a time representation, for filesystem timestamps, etc. We REALLY don't want to deal with the problem that our representation is inadequate in some reasonably future time. Also, since the 64 bits is signed, times back to 28,000 BC can be represented. This is potentially useful for astronomical data, and happily, includes all of recorded history. If we decreased the resolution, we would give up range. This choice seemed like a reasonable compromise. 2) Since we include the the transmission delay in the inaccuracy, 100 ns represents only 30 meters. Its not meaningful to talk about synchronizing clocks below that level with our algorithm. (I believe its not meaningful to talk about synchronizing clocks below that level with NTP either). The total timestamp is 128 bits, this includes a four bit version number field which would permit these decision to be revisited in the future. ... With respect to applications involving precision time data, such as national standards laboratories, resolutions less than the 100 nanoseconds provided by DTS are required. Present timekeeping systems for space science and navigation can maintain time to better than 30 nanoseconds, while range data over interplanetary distances can be determined to less than a nanosecond. While an ordinary application running on an ordinary computer could not reasonably be expected to expect or render precise timestamps anywhere near the 200-picosecond limit of an NTP timestamp, there are many applications where a precision timestamp could be rendered by some other means and propagated via a computer and network to some other place for processing. One such application could well be synchronizing navigation systems like LORAN-C, where the timestamps would be obtained directly from station timekeeping equipment. There is an obvious inconsistency in your position here. If you're just using the NTP time format for synchronization, then talking about 136 year rollovers makes some sense. It could be hidden from the users by extending the protocol. If, however, as this paragraph implies you intend the NTP time format as a general timestamp, then there will be extreme pain in the year 2036. (This is refered to in DEC as the "date75" problem!) To avoid this without unduly extending the timestamp DTS has traded off being able to use its timestamp format for certain highly precise applications. NTP specifically and intentionally has no provisions anywhere in the protocol to specify time zones or zone names. The service is designed to deliver UTC seconds and Julian days without respect to geographic position, political boundary or local custom. Conversion of NTP timestamp data to system format is expected to occur at the presentation layer; however, provisions are made to supply leap- second information to the presentation layer so that network time in the vicinity of leap seconds can be properly coordinated. DTS includes provision for time zones and presumably summer/winter adjustments in the form of a numerical time offset from UTC and arbitrary character-string label; however, it is not obvious how to distribute and activate this information in a coordinated manner. The information is used only as a help in user displays. That is, an application can display BOTH the UTC time and the local time at which a timestamp was created. It only cost 12 bits to do this. No use is made of the timezone information by DTS or by systems. ... The accuracy and stability expectations of NTP preclude this approach. In NTP the incidence of leap seconds is assumed available in advance at all primary servers and distributed automatically throughout the remainder of the synchronization subnet as part of normal protocol operations. Thus, every server and client in the subnet is aware at the instant the leap second is to take affect, and steps the local clock simultaneously with all other servers in the subnet. Thus, the local clock accuracy and stability are preserved before, during and after the leap insertion. Each server has to maintain and propagate this state before the leap insertion. This is, of course, subject to Byzantine failures. A failing server can insert a bad notification. ... In NTP the roundtrip delay d and clock offset c of server B relative to A is d = (t4-t1) - (t3-t2) c = ((t2-t1) + (t3-t4))/2. This method amounts to a continuously sampled, returnable-time system, which is used in some digital telephone networks [LIN80]. The derivation of the expression for 'c' above assumes the two transit delays for this exchange are symmetric. If there are systematically asymmetric transmission delays then the NTP algorithm will shift the two clocks so that they appear to be synchronized, when in fact they are systematically off by some number of milliseconds. The NTP minimum filter attempts to minimize this effect assuming that the shortest round trip exchange would have to be symmetric or nearly so. Unfortunately quite large systematic asymmetric delays can occur for a variety of reasons: source-routed networks, broken routing tables, etc. and these would apply to all transactions including the shortest. This problem exists in DTS also, but in DTS both of the systems will have an inaccuracy which encompasses the correct time. That is, DTS will not claim to have synchronized clocks to a level which it has not, even in the presence of asymmetric delays. NTP can and has. ... Both NTP and DTS have to do a little dance in order to account for timing errors due to the precisions of the local clocks and the frequency offsets (usually minor) over the transaction interval itself. A purist might argue that the expression given above for delay and offset are not strictly accurate unless the probability density functions for the path delays are known, properly convolved and expectations computed, but this applies to both NTP and DTS. The point should be made, however, that correct functioning of DTS requires reliable bounds on measured roundtrip delay, as this enters into the error budget used to construct intervals over which a clock can be considered correct. However, this is not at all hard to compute. Simply increase the inaccuracy by the potential drift of the local clock during the transaction. The architecture specifies this. ... NTP maintains for each server both the total estimated roundtrip delay to the root of the synchronization subnet (synchronizing distance), as well as the sum of the total dispersion to the root of the synchronization subnet (synchronizing dispersion). This synchronizing distance has a rather loose definition. I believe the current NTP RFC suggests using ten times the mean expected error for the synchronizing distance. If this parameter is important to the NTP algorithm I would expect some stronger specification. Also, where does the value ten come from? I know its experimentally derived and seems to work ... These quantities are included in the message exchanges and form the basis of the likelihood calculations. Since they always increase from the root, they can be used to calculate accuracy and reliability estimates, as well as to manage the subnet topology to reduce errors and resist destructive timing loops. While you state the synchronizing distance and sychronizing dispersion can be used to calculate accuracy, I have never seen a derivation of how this could be done. This is one of the recurring points, the lack of formal proofs. ... The next step is designed to detect falsetickers or other conditions which might result in gross errors. The pruned and truncated candidate list is re-sorted in the order first by stratum and then by total synchronizing distance to the root; that is, in order of decreasing likelihood. A similar procedure is also used in Marzullo's MM algorithm [MAR85]. Next, each entry is inspected in turn and a weighted error estimate computed relative to the remaining entries on the list. The entry with maximum estimated error is discarded and the process repeats. The procedure terminates when the estimated error of each entry remaining on the list is less than a quantity depending on the intrinsic precisions of the local clocks involved. A point which is not discussed here is that when NTP chooses to prune an entry, it can not determine if this entry's problem is that it comes from a bad clock (falseticker in your jargon), or experienced unusually large and asymmetric network delays. The latter case is something to be expected in normal operation, the former represents a problem which should be fixed. DTS uses the interval information to identify such bad clocks, and reports them. Since if a clocks interval doesn't intersect the majority it is clearly faulty. This is, of course, a MAJOR issue in distributed system management. ... The fundamental assumption upon which the DTS is founded is Marzullo's proof that a set of M clocks synchronized by the above algorithm, where no more than j clocks are faulty, delivers an interval including UTC. The algorithm is simple, both to express and to implement, and involves only one sorting step instead of two as in NTP. However, consider the following scenario with M = 3, j = 1 and containing three intervals A, B and C: A +--------------------------+ B +----+ C +----+ Result +-----================-----+ Using the algorithm described in the DTS functional specification, both the lower and upper endpoints of interval A are in M-j = 2 intervals, thus the resulting interval is coincident with A. However, there remains the interval marked "=" which contains points not contained in at least two other intervals. The DTS document mentions this interesting fact, but makes a quite reasonable choice to avoid multiple intervals in favor of a single one, even if that does in principle violate the correctness assumptions. Come on, this in no way violates the correctness assumption. The proofs tell us that the correct time is somewhere in the two dashed sub- intervals. By making the statement that the time is somewhere in the larger interval, a server is making a WEAKER assertion. Marzullo's proof would apply and the algorithm would work (sub-optimally) if servers arbitrarily lengthened the intervals they computed. ... In point of fact, the local clock model described in the NTP specification is listed as optional in the same spirit as the model described in the DTS functional description. As such, the local clock can in principle be considered implementation specific and not part of the formal specification. This is a rather odd statement. What I read is that the local clock model is not explicitly required by the NTP documents, but it is, in fact, required in functioning implementations. However, as demonstrated above, frequency compensation requires the local clock adjustment to be carefully specified and implemented. The NTP mechanism has been carefully analyzed, simulated, implemented and deployed in the Internet, but DTS has not. I have never read a clear specification of the required quality of the input time to NTP. However, the following argument shows that in a LAN of typical machines, DTS can indeed provide time to NTP. The clock resolution of most machines is between 1 and 16.7 milliseconds. Thus, any single measurements made by NTP MUST experience this clock jitter. NTP can achieve better overall results only by averaging many such measurements. We have measured the 'jitter' of DTS times in LANs, it is less than 10 milliseconds, so if DTS supplies time to NTP in a typical LAN, the NTP will receive time similar in quality to the time it gets from other NTP servers. In the WAN case, the jitter may be a problem, I assume that to interoperate in the presence of WAN links may require clock training. If you could provide the derivation of accuracy from synchronization distance and synchronization dispersion that you allude to in section 4.2, this could form the basis of reliable interoperation with NTP supplying time to DTS. Alas, I suspect such a derivation is unachievable. However, for installations which are not concerned with the DTS guarantee, the time provider interface could be used to import NTP time into DTS (just like any time provider, though there would have to be a user supplied inaccuracy, based on local experience with NTP). We intend to include a sample time provider program to permit this. ... It is an uncontested fact that computer systems can be badly disrupted should apparent time appear to warp (jump) backwards, rather than always tick forward as our universe requires. Both NTP and DTS take explicit precautions to avoid the local clock running backwards or large warps when running forwards. However, both NTP and DTS models recognize that there are some extreme conditions in which it is better to warp backwards or forwards, rather than allow the adjustment procedure to continue for an outrageously long time. The local clock is warped if the correction exceeds an implementation constant, +-128 milliseconds for NTP and ten minutes for DTS. The large difference between the NTP and DTS values is attributed to the accuracy models assumed. I believe the difference also comes from different assumptions of the risks (and probabilistic costs) involved in jumping the clock. We assume it is something you want to do rarely. For most servers and transmission paths in the Internet a offset spike (following filtering, selection and combining operations) over +-128 milliseconds following filtering, selection and combining operations is so rare as to be almost negligible. The duplicated text makes me think there is something wrong here, though frankly I don't understand what this paragraph is trying to say. ... The service objectives of both NTP and DTS are substantially the same: to deliver correct, accurate, stable and reliable time throughout the synchronization subnet. However, as demonstrated in this document, these objectives are not all simultaneously achievable. For instance, in a system of real clocks some may be correct according to an established and trusted criterion (truechimers) and some may not (falsetickers). the models used by NTP and DTS the distinction between these two groups is made on the basis of different clustering techniques, neither of which is statistically infallible. A succinct way of putting it might be to say that NTP attempts to deliver the most accurate, stable and reliable time according to statistical principles, while DTS attempts to deliver validated time according to correctness principles, but possibly at the expense of accuracy and stability. I would claim you're understating DTS's goals of autoconfigurability and managablility. In both the NTP or DTS models the problem is to determine which subset of possibly many clocks represents the truechimers and which do not. An interesting observation about both NTP and DTS is that neither attempts to assess the relative importance of misses (mislabelling a truechimer as a falseticker) relative to false alarms (mislabelling a falseticker as a truechimer). In signal detection analysis this is established by the likelihood ratio, with high ratios favoring misses over false alarms. In retrospect, it could be said that NTP assumes a somewhat lower likelihood ratio than does DTS. I'm not sure I understand your jargon here. The important trade off for DTS is to notify managers of broken clocks (calling a falseticker a falseticker) so that it can be fixed. Declaring a good clock bad (labeling a truechimer a falseticker) could only occur in DTS as an implementation error or as a massive multi-server failure. In either case a human will have to get involved. It might be concluded from the discourse in this document that, if the service objective is the highest accuracy and precision, then the protocol of choice is NTP; however, if the objective is correctness, then the protocol of choice is DTS. However, the discussion in Section 4.2 casts some doubt either on this claim, the DTS functional specification or this investigator's interpretation of it. I believe you are doing your position a disservice by raising this red- herring. No one has found your argument that DTS violates the assumptions of Marzullo's thesis convincing. Lamport commented that it indicates a serious misunderstanding of Marzullo's proof. It is certainly true that DTS is "simple" and NTP is "complex," but these are relative terms and the complexity of NTP did not result from accident. That even the complexity of NTP is surmountable is demonstrated by the fact that over 2000 NTP-synchronized servers chime each other in the Internet now. The ever decreasing cost of time providers argues heavily for a simple solution, even though it may require more time providers. It simply isn't worth a lot of software complexity, (and maintenance cost, and management cost) to avoid spending a few dollars to buy more providers. Further, the philosophy of 'correctness' leads to certifiable implementation by independent vendors. ... The widespread deployment of NTP in the Internet seems to confirm that distributed Internet applications can expect that reliable, synchronized time can be maintained to within about two orders of magnitude less than the overall roundtrip delay to the root of the synchronization subnet. For most places in the Internet today that means overall network time can be confidently maintained to a few tens of milliseconds [MIL90a]. While the behavior of large-scale deployment of DTS in internet environments is unknown, it is unlikely that it can provide comparable performance in its present form. With respect to the future refinement of DTS, should this be considered, it is inevitable that the same performance obstacles and implementation choices found by NTP will be found by DTS as well. I disagree with this final paragraph. I think that NTP and DTS both attain their very different goals. Our difference of opinion is in how important the different goals are. I accept that DTS will not keep clocks quite as tightly synchronized as NTP. It will, however, be a product that a vendor can confidently ship to customers who are expected to install, configure and manage it themselves. ------------------------------------------------------------------------ Date: Mon, 19 Mar 90 14:19:44 EST From: Dennis Ferguson To: Mills@udel.edu, comuzzi@took.dec.com, elb@mwunix.mitre.org, marcus@osf.org Subject: Re: Review and comment on comparison of DTS and NTP I have avoided more than a brief comment on DTS since my copy was compressed two pages onto a page and then FAXed to a really rotten FAX machine here. It is half unreadable, and I have been a little reluctant to get involved in this for fear I might attribute to DTS shortcomings which are dealt with in the parts I can't read. I don't, however, feel my particular concerns about DTS have been adequately dealt with by what has passed so far. As a consumer of time I care only about results, and what is required of me to achieve them. In particular I care about three things: that my computer's system clock be as accurate as possible as much of the time as possible for a reasonable expenditure of CPU cycles and network bandwidth, that I not have to work too hard to achieve this, and that I have some way of verifying the truthfulness of the time I am receiving. Note that how accurate is "accurate" is hardly quantifiable, the clock should provide the time as accurately as is possible within the constraints stemming from hardware and network deficiencies. Similarly, I would like to do no work to achieve this other than starting a program. The "truthfulness" part is important since one of the major application groups which will require time synchronization will no doubt be authentication protocols (e.g. SNMP authentication, and Kerberos to some degree) and I don't want to leave a hole for attacking these through the time protocol. In this light I'd like to make some comments on the recent round of debate concerning DTS versus NTP. NTP is a solution for the frequency market. DTS is only interested in the time-of-day market. The major cost for these solutions is not the initial capital investment, but the long term management and operation cost. As such DTS has goals of auto-configurability and ease of management which are not present in NTP. This is blatantly misleading. NTP is more accurate than DTS because it includes computational machinery to condition the local clock, which DTS lacks. DTS includes a sub-protocol for autoconfiguring a large portion of the synchronization subnet, NTP does not (or at least not on the scale of DTS). All this is true. What is misleading is the strong implication that these issues are somehow related. They are completely and utterly orthogonal. NTP could be enhanced with an auto-configuration protocol, and indeed could use a variant of DTS' scheme, without affecting the precision it achieves one wit. Similarly, DTS' omission of the local clock machinery was in no way necessitated by its ability to auto-configure, nor any other aspect of the protocol which I can fathom. DTS just left this part out, and as a consequence is sloppier. The "time-of-day market" versus "frequency market" analogy is hence quite faulty, I think. I can see no cost at all associated with NTP's precision, perhaps other than requiring additional work on the part of the implementer of the software. As stated above, DTS is addressing the time-of-day market hence high frequency stability is an not a goal of DTS. Again, this is so silly. As far as I can see, DTS has gained exactly nothing by leaving out the local clock conditioning code, but has lost an order of magnitude or more in accuracy under normal conditions and several orders of magnitude should the subnet partition and cause loss of reachability of the radio clock servers. Just saying this "is not a goal of DTS" with the "time-of-day market" irrelevancy thrown in does not make this reasonable. This from Dave Mills, followed by Joe Comuzzi, followed by Dave Mills: There does not appear to be a multicast function in which a personal workstation could obtain time simply by listening on the local wire without first obtaining a list of local servers. That is correct, it would violate the principle that a message exchange has to happen in order to correctly assign an inaccuracy. There appears to be a considerable Internet constituency which has noisily articulated the need for a multicast function when the number of clients on the wire climbs to the hundreds. Having responded to the articulation noise, I thought it might be a reasonable idea to include this capability (so far untested) on LANs with casual workstations, promiscuous servers and simple protocol stacks. This capability is certainly not untested. My NTP daemon does multicasting, and I synchronize about 80 machines here this way (I also note that 8/9ths of the computers which make up the NSFnet backbone are also time synchronized with broadcast NTP. I have no idea how many other users there are). The clients which are synchronized this way require no configuration and, indeed, the scheme scales well since I could synchronize 100's of machines this way at no additional expense. The NTP clock filter is adaptable for use with one-way time, the selection algorithms continue to work as always, and systematic time skews between machines with precise clocks are on the order of a few milliseconds (and stably so. This is NTP, after all). Truthfully, while I like the DTS approach to clock combination, I'm not sure I care about knowing the inaccuracy enough to miss knowing it on hosts at the bottom of the synchronization tree. Multicast time seems to me to be a feature the "time-of-day market" could truly make good use of. The DTS time is a signed 64 bits of 100 nanoseconds since Oct 15, 1582. It will not run out until after the year 30,000 AD. Unlike NTP which will run out in 2036. I, for one, intend to still be alive in 2036! Note that this comment is only relevant if one requires that time stamps for long lived things like files be identical to timestamps used by the time synchronization protocol. I see no reason to require this, about the only thing you save are a couple of conversion routines. If this isn't a requirement then the only thing NTP has to worry about are packets which spend more than 136 years in transit, and that there be some external time source which allows you to determine the time-of-day to within 68 years before running the protocol. I can't get too excited about this. 2) Since we include the the transmission delay in the inaccuracy, 100 ns represents only 30 meters. Its not meaningful to talk about synchronizing clocks below that level with our algorithm. (I believe its not meaningful to talk about synchronizing clocks below that level with NTP either). I have some 68000-based hardware with microsecond system clocks which have an on-time second output I can look at with an oscilloscope, or plot on a chart recorder. The clocks have ovenized crystal oscillators. I see synchronization between the machines, via NTP across an ethernet, on the order of 50-75 us (after calibrating out systematic asymmetric delays in the code). This is hardly trying, either. I don't think 100 ns is particularly small. GPS can give me UTC more precisely than that, I don't think it unreasonable to expect time synchronization protocols to be prepared to move time with precisions I can get today, let alone 20 years from now. From Dave Mills, followed by Joe Comuzzi: Both NTP and DTS have to do a little dance in order to account for timing errors due to the precisions of the local clocks and the frequency offsets (usually minor) over the transaction interval itself. However, this is not at all hard to compute. Simply increase the inaccuracy by the potential drift of the local clock during the transaction. The architecture specifies this. What bugs me about this is that increasing the inaccuracy by the potential drift (it appears to me the latter must be configured as well, since DTS doesn't seem to include any machinery to determine it on the fly. DTS may not be quite as "manageable" as one might believe) may make the protocol work nicely, but doesn't do a damn thing for the precision of my drifting system clock. The latter is what I'm paying for a time synchronization protocol for, the fact that DTS can tell me it is doing a bad job by giving me error bounds doesn't excuse the fact that it is doing a bad job. It appears to me that the NTP local clock code is a natural for DTS. It avoids having to configure an expected drift to get a realistic estimate. It essentially reduces the drift by more than an order of magnitude. Since the local clock algorithm is analitically well defined it should be quite possible to have it produce a meaningful inaccuracy for use by the protocol automatically (the compliance estimate is close already). The inclusion of the local clock conditioning code would affect little else that I can see. Why didn't DTS include it? A point which is not discussed here is that when NTP chooses to prune an entry, it can not determine if this entry's problem is that it comes from a bad clock (falseticker in your jargon), or experienced unusually large and asymmetric network delays. The latter case is something to be expected in normal operation, the former represents a problem which should be fixed. DTS uses the interval information to identify such bad clocks, and reports them. Since if a clocks interval doesn't intersect the majority it is clearly faulty. This is, of course, a MAJOR issue in distributed system management. The possibility of separating broken clocks from broken networks is a neat feature of DTS' approach, and one much to be desired. I covet this ability. But why, oh why, was local clock conditioning ignored and the accuracy of the system clock compromised? I covet the latter more intensely, and can't understand why I can't have both. I have never read a clear specification of the required quality of the input time to NTP. However, the following argument shows that in a LAN of typical machines, DTS can indeed provide time to NTP. The clock resolution of most machines is between 1 and 16.7 milliseconds. Thus, any single measurements made by NTP MUST experience this clock jitter. NTP can achieve better overall results only by averaging many such measurements. We have measured the 'jitter' of DTS times in LANs, it is less than 10 milliseconds, so if DTS supplies time to NTP in a typical LAN, the NTP will receive time similar in quality to the time it gets from other NTP servers. In the WAN case, the jitter may be a problem, I assume that to interoperate in the presence of WAN links may require clock training. It is incorrect that the NTP local clock must experience a jitter of the magnitude of the precision of the remote machine's clock, since this data is passed through the filter algorithm before it reaches the clock. What mystifies me is where the 10 milliseconds comes from and how this is typical. I am on thin ice here, but let me expose my ignorance by making some assertions based on what I can decode from the DTS spec. DTS seems to be designed to deal with clock drifts in the 100 ppm ballpark. It appears to me that the clock is updated once in 15 minutes (??). Without clock conditioning, this would imply that a DTS synchronized clock may jitter by 90 ms over the update period, and that on average the clock will be 45 ms off (this may be incorrect, but I see nothing at all in there which compensates for drift with predictive adjustments). This is what is alarming, an NTP-corrected clock likely won't drift by 90 ms if left without synchronization for 2 or 3 days, and under normal operation when synchronized across a LAN will on average be right dead on (or, at least, show systematic offsets in the sub-milliseconds which are more related to code path lengths and such). There is no reason why DTS couldn't match this performance. Now, either your 10 ms implies that the "typical" clock you tested with had an inherent drift of less than 10 ppm, or that I am grossly mistaken and the clock update interval is more like a minute-and-a-half (implying a lot of traffic?). If the latter is true, I apologize. If the former is true, however, I would suggest you may be in for a big shock when you try to run your protocol in the "real world". From data taken from about 275 machines which run NTP here, we see an *average* drift of 30 ppm slow, with quite a large standard deviation. Fully 5% of those machines have drift rates greater than the 100 ppm (I note that none of these are built by DEC, which may be why DTS has a more optimistic view of the world). There are six workstations in the room next door which drift at a rate of 300-350 ppm fast. NTP handles all of these (though it was helped with the 300 ppm stations by some priming), and the local clock effectively reduces the drift rate to a ppm or less in almost all cases. DTS leaves this part grossly underengineered. It is an uncontested fact that computer systems can be badly disrupted should apparent time appear to warp (jump) backwards, rather than always tick forward as our universe requires. I believe the difference also comes from different assumptions of the risks (and probabilistic costs) involved in jumping the clock. We assume it is something you want to do rarely. Both Dave and Joe miss a fundamental point here. There is nothing in the NTP spec which requires the system clock (as opposed to NTP's local clock) to step into a +-128 ms window, or a +-512 ms window, or into a 15 minute window for that matter. NTP need never step the system clock backwards. There is a compilation option to my daemon which causes it to slew the system clock under all conditions, as this closes a hole when used with Kerberos. The performance when done this way is very nearly identical to the performance when the system clock is allowed to step. NTP's stepping of the system clock is an absolute non-issue, it can do it any way you prefer. A succinct way of putting it might be to say that NTP attempts to deliver the most accurate, stable and reliable time according to statistical principles, while DTS attempts to deliver validated time according to correctness principles, but possibly at the expense of accuracy and stability. I would claim you're understating DTS's goals of autoconfigurability and manageability. I would claim that all of the above is misleading. (1) There is no reason that I can see why DTS' accuracy and stability couldn't be improved to NTP levels without violating correctness principles. Indeed, such an enhancement could only improve DTS' error bound estimate since it seems to me the local clock could be used to automatically produce estimates of things that need to be configured now. (2) NTP's accuracy and stability in no way preclude additions to the protocol to ease configuration and management. The latter just hasn't been done yet. (3) DTS' autoconfigurability and manageability have nothing to do with its ability to achieve NTP's level of performance, or lack thereof. The computational machinery required to do the latter was omitted for no good reason that I can see. The ever decreasing cost of time providers argues heavily for a simple solution, even though it may require more time providers. It simply isn't worth a lot of software complexity, (and maintenance cost, and management cost) to avoid spending a few dollars to buy more providers. Further, the philosophy of 'correctness' leads to certifiable implementation by independent vendors. I continue to believe it is not constructive to "certify correctness" in probabilistic systems, only to exchange acceptable tolerance bounds for acceptable error bounds. If by "time providers" you imply each is associated with a radio clock, I do not think it likely that the cost of a radio clock will plummet to the point that every LAN can afford one and, even if it did, you can not trust a single radio. You have to have more than one of them and, preferably, no common point of failure between them. I find myself in agreement, and disagreement, with both of these points of view. I am personally a believer that every LAN should have a "time provider" or three, and that the only thing which prevents this from happening is a chicken-and-egg problem (radio clocks are low volume items and hence are expensive. Radio clocks are expensive, so not a lot of people want to buy them). Again and again, however, the issue of the maintenance and management cost versus performance tradeoff rears its ugly head. *There* *is* *no* *such* *tradeoff*, the issues are orthogonal. Moreover, since the local clock processing is utterly divorced from the rest of the protocol, and since NTP's local clock is far and away the part of the spec most solidly supported by analysis, I can see no reason whatsoever that its inclusion in DTS would affect one's ability to produce certifiable implementations in any way. ... The widespread deployment of NTP in the Internet seems to confirm that distributed Internet applications can expect that reliable, synchronized time can be maintained to within about two orders of magnitude less than the overall roundtrip delay to the root of the synchronization subnet. For most places in the Internet today that means overall network time can be confidently maintained to a few tens of milliseconds [MIL90a]. While the behavior of large-scale deployment of DTS in internet environments is unknown, it is unlikely that it can provide comparable performance in its present form. With respect to the future refinement of DTS, should this be considered, it is inevitable that the same performance obstacles and implementation choices found by NTP will be found by DTS as well. I disagree with this final paragraph. I think that NTP and DTS both attain their very different goals. Our difference of opinion is in how important the different goals are. I accept that DTS will not keep clocks quite as tightly synchronized as NTP. It will, however, be a product that a vendor can confidently ship to customers who are expected to install, configure and manage it themselves. Again the implication that a time protocol which is configurable and manageable cannot be precise. It is not that DTS cannot be precise, it is that it is not precise. I still have yet to see even one clear, understandable advantage which has been gained by not making DTS precise. If I had to choose, I'd send both protocols back to the drawing board for further revision. NTP badly needs some work done in the area of auto-configuring large synchronization subnets, since this can be painful. DTS compromises its precision by ignoring relatively simple, straight forward, analitically sound techniques for improving the behaviour of the local clock, a deficiency which buys it nothing in other areas that I can see. DTS' "correctness" philosophy is truly attractive to me. If we were comparing paper protocols I would rate DTS a hands down winner. The thing is, "correctness" carries less weight with me in the comparison to NTP since NTP is a protocol derived from long practical experience and which is known to work well in the real world. Unless I am misunderstanding something (a distinct possibility), the "10 ms typical" problem may indicate that DTS' idea of what the world is like might not be based on wide experience. I like DTS, though. I just wish the spurious omission of computational machinery to deal properly with the local clock were fixed before international standardhood forces sloppy timekeeping (or, at least, a lot sloppier than it has any good reason to be) on us all. The only other concern I had was related to authentication. I just wanted to make sure either that DTS was only being targetted for the OSI environment or that it was carrying over all the related authentication baggage required into the Internet environment. Given the dependence of other Internet protocols' authentication schemes on the security (and synchronization, even) of the system clock, I think an Internet time protocol which lacks authentication will be unusable in a rapidly growing number of situations (of course, NTP could really use some help in the area of key management, regardless). ------------------------------------------------------------------------ Date: Wed, 21 Mar 90 14:10:08 PST From: comuzzi@took.enet.dec.com To: mills@udel.edu Subject: I've sent this to everyone else, yours bounced because of a typo. This is a note to continue the DTS/NTP comparison, because I too am finding this conversation fruitful. Dennis, I would be glad to mail you a copy of the DTS architecture if you want one. (and Dave, I've even changed the cover and introduction). I'd like to address some of the issues Dennis raised. I'll save his major point, about accuracy and ease-of-managment being orthogonal, for last. Allow me to start with the decision of DTS not to support a multicast mode. One reason was that protocols which multicast the time will be subject to Byzantine failures. (Clearly anyone can just multicast any time they want. This problem does not occur with using multicast to locate the servers in the DTS architecure, multiple servers would have to be co-opted.) The second point, the one I was trying to raise in my reply to Dave, was that it was DTS's intention to have the time and interval information available on every node. The hope was that this would permit the proliferation of applications and algorithms which used the DTS guarantee (that UTC is contained in the interval). Clearly, until such a facility is available on every system, few are going to spend a lot of time exploring such issues. One such application is in DECnet/OSI phase V management. Events are logged with their time and inaccuracy. This permits a network admistrator to examine log entries and determine that one event could not have caused a second event (if, for instance, the interval of the first event doesn't overlap and is later than the second.) Obviously this requires the inaccuracy to be available on every source of events, that is, every node. The third point I'd like to discuss refers to Dave's statement about a "considerable Internet constituency which has noisily articulated the need for a multicast function when the number of clients on the wire climbs to the hundreds." Is it that they wanted multicast? Or was the real objection the practical difficulty of adding a second server to a LAN of 300 nodes and then having to change the server entry in 150 ntp.conf files to redistribute the load? (This is a concrete example of why I claim NTP is a system admistrator's nightmare. However, my real interest in this discussion is to separate the problem (autoconfiguration) from the particular solution that was chosen (multicast the time), and to understand what the motivation of the Internet community was.) Clearly DTS responds to the autoconfiguration problem, but if the requirement really was that they didn't want to add that additional server at all then a multicast scheme is probably the only solution. However, one should be clear about what is being traded- off, a multicast solution will manifestly have Byzantine failures. I think this difference is an interesting one and would like to have more discussions about it. The next topic I'll discuss is the area of the DTS architecture I personally believe is least likely to survive the standardization process unchanged: The timestamp format. I think we have much agreement here. I defended the 100 nanosecond resolution of the DTS timestamp, though I'm not particularly happy with it either. I do think it would be a win if the network timestamp format equaled the internal timestamp format, which argues that the network time format wants to be long lived. Even if this argument is rejected, however, there is still a price to be paid when the network timestamp runs out - implementations which haven't added the rollover code will be unable to operate. The question here is how low-level, pervasive and long-lived network nodes might become (I've heard suggestions of putting the OSI protocol stack in a thermostat, I suppose it could happen.) It's true that sitting here today, it's hard to imagine that any code I write will still be executing in 2036, butif I were blasting it into ROM I'd be less sure about that. I guess I'm also attracted to Dave's suggestion of using Julian Day numbering and fractions within the Julian Day, though when I try to plug in the numbers and actually design the timestamp I'm forced to conclude the total timestamp would have to be a bit bigger. Since I've already heard grumbling about the size of DTS's 128 bit timestamp, I guess I'll have to think about this further. There has been a fair amount of discussion about interoperation of the two time services. Let me try to clarify what I said (too tersely) in my original response to Dave's paper. There are three separate cases I'd like to distinguish A) An isolated group of DTS systems which obtain time from NTP B) An isolated group of NTP systems which obtain time from DTS. C) A collection of DTS and NTP giving time to each other. I believe that without fairly major changes in one or both of the architectures case C is a problem, however it is an easily prevented problem (see below). Cases A and B however are very interesting, useful and I claim easily achievable. NTP giving time to DTS would make sense in environments where DTS systems are being added to LANs where there is no local time provider and there is a pre-existing NTP infastructure. The model for how to do this would be to use the DTS time provider interface to import the NTP time. Comparison of DTS timestamps within the DTS group would work normally; there would, however, be some risk of getting an incorrect result if timestamps of two such groups were intercompared. This risk can be managed though, the interoperation would require the user specify an inaccuracy for the NTP time based on the local experience with NTP, the obvious choice would be some multiple of the synchronization distance - the more risk adverse the larger the multiple. This would (at low probability) violate the DTS correctness philosophy. If you want certainty, buy two hardware time providers per LAN. Note, however, a reasonable compromise would be one hardware time provider and an NTP time provider. The DTS fault detection would check the hardware against NTP and complain when there was a discrepancy. Case B corresponds to situations where a DTS infastructure exists (or is being added) and there is a need to deliver time to systems using NTP. This is the situation I was talking about in my response to Dave. I made several assumptions, which I didn't make clear. I assumed that the gateway would be both a DTS server and an NTP server, that the NTP code would be operating in the "don't change the clock" mode (In the U or Maryland implementation this is the -s option, I'm told Dennis's implementation has an option in the ntp.conf file to do the same thing.) and that the NTP clients were on the same LAN. DTS servers synchronize with each other at two minute intervals (Note this is server to server - clients synchronize at 15 minute intervals. This is Dennis's question.) Now, I'm not claiming that "the NTP local clock must experience a jitter of the magnitude of the precision of the remote machine's clock," what I am claiming is that in normal NTP operation the input data to the NTP filtering algorithm must experience a jitter of the magnitude of the precision of the remote machine's clock. This is the same magnitude as the jitter of the DTS managed clock. I have conducted experiments with this configuration and haven't experienced any wild instabilities. Again, NTP timestamps generated in two such groups will not be intercomparable with each other to the level that they would if the time was being delivered by NTP all the way. Currently however, no application can be algorithmicly depending on distributed time derived from NTP unless the algorithm contains a parameter which says "times closer together then this will be assumed unordered", that is, unless the algorithm imputes an inaccuracy to the NTP time. Case C potentially breaks the invariants of both protocols. The DTS invariant is that UTC is contained within the interval. The NTP invariant (I'm less sure of my statement here) is that the frequency of good servers agree with UTC. NTP has a further invariant, that there are no loops in the time distribution network. This is enforced by the stratum. Clearly if DTS took time from a collection of NTP servers and later gave it back to the same collection of servers, a loop could and probably would occur. There is a simple method to prevent this, I propose that the gateway described in case B above always declare itself to be at some fairly high (numerically large) stratum. Potential clients will ignore the DTS/NTP server in favor of servers which obtained their time exclusively via NTP (and have much lower stratum numbers). I'm assuming that the NTP implementation at the gateway can be coerced into using a fixed stratum and would propose a value of 16 for this purpose. There's also a stratum zero which is supposed to be used when the stratum is unknown, however I'm not sure I understand what value servers which obtain their time from a stratum zero server will use. Do they use zero? If so, how are loops prevented amongst themselves? A few nits before we get to the meat of the discussion. Dennis is concerned that the drift has to be input as a management parameter. I'll show my vendor colors here and say this isn't a management parameter but an implementation detail. The assumption is that when DTS is shipped to you from your hardware or software vendor, the drift has been autoconfigured. That is, a good implementation of the DTS architecture would know the maximum drift rate for the machines that the implementation has been certified on. Until some sort of architecture neutral distribution format (OSF is attempting to settle on such an ANDF) is created this is really easy to do - Just hard code in the value that's appropriate for the given processor family. If there's wide variation within the processor family (or if there are multiple processor families due to an ANDF), you'll have to code a table. About the only case where the user would have to enter it is where he's created his own custom hardware configuration. I guess that doesn't bother me. The second nit has to do with DTS's treatment of leap seconds. I appear not to have been clear here. Dave's original document was basically correct in its description of how DTS handles leap seconds - Servers increase their inaccuracy at the month boundary and a time provider narrows the interval later. When I wrote: "Each server has to maintain and propagate this state before the leap insertion. This is, of course, subject to Byzantine failures. A failing server can insert a bad notification." I was describing my understanding of (and a problem with) NTP's leap second handling. If my understanding of NTP is incorrect, I apologize, but the Byzantine problem seems real to me. In my reply to Dave I stated "DTS will not claim to have synchronized clocks to a level which it has not, even in the presence of asymmetric delays. NTP can and has." Dave correctly points out that "NTP does not claim to have synchronized to any level, only to minimize the level of probablistic uncertainty and estimate the error incurred." I retract the last sentence. What I was trying to say is that DTS makes it clear to the user he could be losing in this way, while NTP does not make it clear. Dave asked if I am in substantial agreement with the statistical models presented in his first document. I agree with most of this section. My only significant disagreement is with the last paragraph. It is true that DTS assumes that a system's clock drifts at a rate less than its manufacture's specification, and that a hardware time provider operates within specification. The probablities of these assumption being false are on the order of magnitude of other hardware failures. Software implementation do not routinely checksum memory any more (and they certainly don't do it to find memory errors). Violations of these assumptions represent faults, just as real as processor faults, and should be fixed. Note the long tails you observe in the distributions in the Internet are on message transmission times and the like. These parameters are dynamically measured in the DTS algorithm. Wick Nichols stated: "DTS is willing to accept historical estimates of the probability that a clock will go faulty (with checks for faultiness), but is not willing to accept historical estimates of current network characteristics." in his discussion of this point for the OSF. Dennis asked a question about DTS authentication in the Internet environment. What I personally would like to see is an implementation of DTS using Apollo's NCS which in turn used Kerberos authentication. This is basically what Digital has proposed to the OSF in response to their distributed computing request for technology. Now to the major contention of Dennis's review, that accuracy and ease- of-management are "completely and utterly orthogonal". I disagree with this less then a reader of my response to Dave might think, though I am somewhat in disagreement with it. What I hold is that ease-of- management, provablility and accuracy for a time service are all interrelated. I believe that ease-of-management is something that must be engineered into a system from the start, it can't be tacked on as an afterthought. Further, I believe simple systems are easier to manage then complex systems. The failure modes that Murphy can find in complex systems are just so much more (for lack of a better word) complex. Now, much of DTS ease-of-management derives from its autoconfiguration, the autoconfiguration is, in turn, dependent on the (relative lack of) configuration rules, that is, that synchronizing any two servers just works and cannot lead to instabilities. The problem with just adding the NTP local clock model to DTS (as I understand the NTP local clock model) is that the resulting system could have wild instabilities. (Maybe my understanding of NTP is incorrect here.) The dynamic nature of the DTS autoconfiguration rules (couriers choosing a random member of the global set for instance) means the the input time driving the local clock model will have what Dave calls "phase noise". As I understand NTP's local clock model this is where the instability creeps in. Further, the existing NTP protocol avoids loops by using a stratum concept, again the DTS autoconfiguration happily produces loops. As I noted previously this doesn't effect the DTS algorithm, but they would cause havoc for NTP. Again one could add complexity to the DTS algorithm to prevent the loops, but I claim one would pay a price in system management cost. Another problem (according to Dave) is that the resultant phase locked loops have to be analyzed in the light of assumed probability distributions, etc. and one does not end up with the sort of proofs of correctness that are what is liked in DTS. There is one interesting aside on this last point. I believe there is a way one could add clock training to the DTS model and preserve the correctness. If the training algorithm decides to change the rate of the clock by some amount, *increase* the maximum drift rate by that amount. I believe this can be shown provably correct by the techniques in Marzullo's thesis. However, while this improves the precision of the time (the intersystem phase differences and rate differences will be smaller) the inaccuracy (the guarantee given to the user) will be worse! That DTS has chosen not to do this is, of course, the basic philosophical difference about what's important showing up again. However, the existance of at least one method to incorporate clock training into a provable system gives hope that both camps can be satified and in particular that the large body of work on the NTP local clock model can be incorporated. I am not (yet) expert enough in the NTP local clock model to see my way through this. The other obvious possibility is to just add the autoconfiguration to NTP. To an extent, this is occuring. The multicast functionallity clearly addreses the ease-of-management issue. However, for NTP servers, I claim that chosing the right server is important enough that it can't be left to an algorithm. Swithing at random between servers reintroduces the clock-hopping problem (the the extra phase noise produced by the clock-hopping will cause problems for NTP.) One could attempt to just pick a set of server at random and stick with them for some long time to reduce clock hopping, but that will produce serious sub-optimality in the case of a changing network configuration (The particular servers being synchronized with might become cut-off from their good time sources, or the paths to them might involve links which become overloaded, and this wouldn't be discovered for a long time.) My desire is a solution which maintaines provability and doesn't require a large tradeoff between autoconfiguration and accuracy. So far the only improvement I can make in the DTS architecture forces me to give up one measure of accuracy to improve another. More work needs to be done here. ------------------------------------------------------------------------ Date: Sat, 24 Mar 90 19:14:56 EST From: Dennis Ferguson To: comuzzi@took.dec.com Cc: Mills@udel.edu, elb@mwunix.mitre.org, marcus@osf.org Subject: Re? More discussion of the differences (and similarities) of DTS and NTP. I realize that, while the NTP local clock processing is not a particularly difficult coding exercise, it rests on a foundation which is the subject of lots of textbooks and quite a number of academic journals. I also realize the presentation in Appendix F of the current NTP document certainly does not derive this stuff from first principles, since that would require turning the NTP spec into another control theory textbook. I can understand the derivation in there (though I couldn't have produced it, and could verify it only with great difficulty) by virtue of a somewhat academic, traditional engineering background (Dave seems to have a very academic, traditional engineering background), but I realize the stuff may look more than a little opague if no one has ever forced you to learn/use that stuff. It is, however, very worth while to get a handle on what is in there, at least functionally, because this can make orders of magnitude difference in the results you get from your time protocol. Let me a number of assertions, some of which I'm not going to be able to support here, but which can be discovered by looking very carefully at the local clock description. I think you will find that it is not what you think. (1) The NTP local clock does for NTP (and potentially for DTS) what adjtime() does for DTS. It is essentially a procedure which is called with a time offset as an argument, and which does something to the system clock as a result. (2) Like adjtime(), the NTP local clock is fully deterministic. There are no probability considerations here. When you give it a time offset, the effect this has on the system clock is fully predictable. Hence the NTP local clock can have no effect on your ability to maintain correctness, any more than the behaviour of adjtime() has any effect on your ability to maintain correctness. The NTP local clock does what it is told, no more and no less. (3) I think the specified NTP local clock is (should be, I have to trust Dave's math for this) unconditionally stable for all input. Note that "stable" in this context has a very specific meaning, and may not be what you expect. If the NTP local clock wasn't unconditionally stable for all input with its current parameters, it could be made that way by adjusting those parameters. The stability of the local clock is predictable. The local clock, in both NTP and DTS, takes time offsets from UTC as input and attempts to adjust the system clock in response to these, in principle to make the offsets smaller. Note that this is a feedback loop, the the adjustments which are made to the system clock affect the next offset which is input to the local clock. Now suppose a DTS client has a clock which drifts by 100 ppm. Suppose it also manages to obtain offsets every 15 minutes, by exchanges with its servers, which represent the difference between the client's system clock and UTC accurately to the nanosecond. The client gives an offset to the DTS local clock, essentially adjtime(), which slews the clock by the amount of the offset, and then sits around waiting for the next offset to arrive. Of course, while adjtime() is slewing the clock towards 0 offset, the clock's drift is slewing it away at a rate of 90 ms per 15 minutes. At the end of fifteen minutes the whole thing will be repeated. Also, as adjtime() will typically slew the clock at a much greater rate than 100 ppm, the system clock offset from UTC will show a sawtooth waveform varying between 0 and 90 ms with a period of 15 minutes, and will average 45 ms off. So, for absolutely perfect data in, the DTS local clock can get the system clock no closer than 45+-45 ms. This is inaccurate (it isn't even meaningful to say that you are getting perfect data in, either, since the jitter will be fed back as an uncertainty in the input). Indeed, this inaccuracy is not unexpected. This is what is called a Type I feedback loop (I think), and is known to be unable to track an input without introducing a phase error on the output. Worse, for perfect data in consumers of time on that machine will see an uncertainty of +-90 ms, even though the true uncertainty is only half that (0 to 90 ms), and even though the input data is perfect. This is gross. The NTP local clock does much, much better, by a couple of techniques. First, the jitter the DTS system clock experiences is essentially eliminated by not feeding an entire adjustment to the system clock all at once, but rather by making very small adjustments at frequent intervals (currently 4 seconds in the spec). The NTP local clock hence avoids introducing the sawtooth, the clock changes slowly and smoothly. Further, the NTP local clock corrects the average error by computing and applying a correction for the drift, by implementing a Type II feedback loop. Essentially, for perfect data in, the NTP local clock will eventually determine the drift of the system clock and, when it does, will maintain the average offset of the system clock at 0. I.e., perfectly accurate. A Type II feedback loop will track a fixed input accurately. By applying many little corrections to the system clock instead of one big one, NTP will also maintain the system clock relatively jitter free (one could say absolutely jitter free in comparison to DTS). Of course, there is no such thing as perfect, but we can begin to assign relative orders of magnitude to errors of the DTS and NTP local clock schemes (this comparison is deterministic as well, there are no probabilities involved). DTS' local clock error is proportional to the drift. NTP's local clock error is proportional to the rate of change of the drift with respect to time multiplied by the time constant of the PLL. In the real world the latter is less than the former by at least several orders of magnitude. I have grossly oversimplified this, but please believe that the details are all in the NTP spec if you decode them. Now, how can replacing DTS' use of adjtime() with something which is more accurate affect DTS' configurability? How could it possibly affect correctness? I stand by my original statement, that the issue of accuracy (with respect to the local clock) is completely and utterly orthogonal to any issues of configuration or management. DTS just didn't include the machinery to condition with the local clock (and apparently is hung up on type I feedback loops for clock control when there are other better ways to do it), and this is what is so frustrating about it. I also think your claim that using local clock processing which does frequency compensation would require one to *increase* the inaccuracy must either be wrong, or indicate that DTS is doing something very silly. Does it make sense that something which can be analytically shown to increase accuracy increases the inaccuracy? Does it make sense that, if I tune a crystal for zero drift in hardware with a screwdriver that the inaccuracy should decrease, while if I tune it for zero drift in software the inaccuracy must increase? The mind boggles. Further, I think you may still be operating in an unreal world with the assertion that a manufacturer could possibly define a maximum drift for the clock in a particular model of machines, one that could never be exceeded under any circumstances which couldn't be called hardware failure. I would suggest to you that the very worst cause of clock drift in real systems is not hardware at all, but rather lost clock interrupts (which cause large, negative drifts). Would you be willing to certify that DEC hardware/operating systems never lose clock interrupts under any circumstances? Or provide a guaranteed limit to the number that will be lost in any time interval? You can call lost clock interrupts a "fault" if you wish, but implying that such "faults" are "historically" a rare occurance flies in the face of experience, at least with Unix systems. Which brings up another assertion I am begining to doubt, that NTP does not (or cannot) know the inaccuracy of its time estimate. Joe, take a look at how NTP's synchronization distance is accumulated. Don't worry about the value of this that the spec suggests be used for stratum 1 servers, let's assume that this is configured for stratum 1 servers in a way which agrees with DTS. Look carefully at how the synchronization distance a stratum 3 server will receive. Do you see any reason why I could not assert that UTC must be contained in an interval which is +- 1/2 the synchronization distance from the system clock's time, and prove this assertion by the same principles that DTS uses? Or, if not, that there are any uncorrectable imperfections in this assertion? I am hence beginning to think as Dave, that NTP's time could be proven to lie within known bounds, just as DTS' can. I see nothing that would prevent this. If applications needed to know this, I think it could be arranged for NTP to provide it. The question becomes, then, what is all that statistical junk that NTP does? I think the issue that is being missed here (and I'm on thin ice again) is that DTS does indeed make some assumptions about probability distributions. In particular, all correctness can give you is an interval which should include UTC. The system clock, however, cannot be set to an interval, it needs a specific value. DTS hence arbitrarily assumes that any time in the interval are equally likely to be UTC as any other, and hence picks the middle of the interval as this minimizes the probable error based on that assumption (the fact that not picking the middle of the interval increases the inaccuracy interval demonstrates a flaw in the DTS protocol which is also exercised by the local clock processing. The protocol demands that the intervals be +- something even when it might be known that the true interval is +something -something-different. DTS hence claims inaccuracy intervals which are often bigger than they should be simply because it lacks the ability to represent the true state of affairs. This doesn't affect correctness, but reduces the utility of knowing the inaccuracy interval). NTP, however, assumes that the probability distribution over the interval is non-uniform, that some times within the interval are more likely to be UTC than others (this isn't strictly true, but I see no reason why it couldn't be). It proceeds to determine the time within the interval which is most likely to be UTC and sets the clock to that. NTP does this in part by casting off samples and servers which it thinks are less reliable. If DTS can correctly synchonize to a single server, however, then casting off servers you aren't fond of can't affect correctness. NTP choses servers it likes (and samples from servers it likes) based on presumed characteristics of the probability distributions of network traffic. This has no effect on correctness, however, and in the extremely unlikely event that the network does not behave in the way that NTP expects, NTP's choice of UTC will probably be no worse than DTS'. This has no effect on NTP's ability (or lack thereof) to produce correct bounds on the estimate, in DTS' sense. Also, I find it strange that DTS could claim that avoiding having to "accept historical estimates of current network performance" is a feature, when this is done by making assumptions about probability distributions which have no basis in practical reality at all. A couple of things come to mind. Joe, you mentioned something about "wild instabilities" which Dave said NTP might suffer in the face of poor server selection, or some such. I would suggest to you that the term "wild instabilities" is one which is relevant only in relation to one's expectation of the performance of your time protocol. To anyone who thinks an error of 45+-45 ms in the time the system clock returns when given perfect data is acceptable, NTP is as solid as a rock. NTP's "wild instabilites" are only relevant if your expectations are much higher than DTS', since "wild" for NTP is a lot smaller than the instabilities DTS apparently considers normal. More than this, I fail to understand the rest of the arguments about why NTP couldn't be retrofitted with an autoconfiguration protocol. NTP has no configuration rules, it places itself in the heirarchy based on the servers available to it. NTP will operate in such a way as to maximize the probable accuracy of its time no matter how it is configured. Give your NTP daemon a random set of peers and it will chose the best of them, adopt a stratum which is appropriate based on the time sources available, and make the best use of the time available. Concerns about "phase noise" (i.e. jitter) are again based on expectations of the performance of the time protocol, an NTP server which takes time from your 45+-45 ms host will survive just fine, and indeed will show far less jitter than +-45 ms (look at the local clock, high frequency noise is damped out). It is just that NTP servers are expected to be a lot closer than 45 ms, so your host looks bad compared to NTP's expectations (but not needs). Further, the stuff about synchonization loops is irrelevant. The NTP protocol survives loops just fine, it's just that the consequence of a loop is that the machines involved count their statum to infinity and disconnect from the synchronization subnet rather than continuing to fool themselves that their servers know something they don't. This is quite reasonable behaviour since NTP clocks don't drift much when left unsynchronized. I would suggest to you that NTP knows far more about Murphy than DTS does at this point, since it has been tested in far more environments, on far more machines, in likely far harsher environments, through far more revisions, for far longer than DTS has. There are three independently done implementations of NTP, all of which work well and interoperate. How complex can NTP be? NTP can be given a random set of servers and work just fine, thanks. This wasn't done with auto-configuration specifically in mind, but rather simply to meet robustness requirements. NTP has a lot of real world experience to prove that it is robust, and that it is certainly robust in the face of even gross misconfiguration. What more is needed for an auto- configurable protocol? Autoconfiguration certainly couldn't do a worse job than people do. As for Byzantine failures, you are right that NTP's scheme for leap second notifications suffers from this, but what is the worst thing that can happen if this occurs? Right, your clock ends up a second off. With DTS, however, it is a virtual certainty that the clock will end up a second off when a leap second occurs, so criticizing NTP for leaving this hole is a little like the pot calling the kettle black. That DTS increases its inaccuracy by a second is irrelevant for comparison, since NTP doesn't maintain this inaccuracy. If (when) NTP maintains an inaccuracy interval it should probably increase it by a second during leaps as well. This doesn't help keep your clock accurate across leaps, though. For broadcast time, however, I think this is incorrect. The NTP clock selection code includes an agreement protocol, and this is still used for broadcast time. To cause a failure one would have to co-opt a majority of the servers, and this is hardly less robust than DTS. I can see little more exposure to such failures with broadcast time than with polled time, and I think we must agree that polled NTP is not less robust in the face of Byzantine failures than DTS. Further, if you are really worried about hostile attacks on your clients then you'll be using authentication anyway, in which case there is no additional exposure to such failures. More than this, note that NTP's multicast time is used in the LAN environment. The transit delays here are a few milliseconds, and indeed my daemon includes partially implemented code to determine these delays on the fly by polling. This transit delay isn't even measureable by a lot of machines (between machines with 10 or 20 ms clocks you end up computing absurdities like negative round trip delays. Does DTS handle this?), so DTS isn't necessarily going to know a whole lot about this delay by polling anyway. Now, you are willing to accept a 45+-45 ms error in the setting of your clock and a 90 ms inaccuracy, for perfect data in, due to the primitive local clock processing that DTS does, why the heck not add in another, say, 50 ms or something equally outrageous, to the inaccuracy interval for the broadcast and forget about it? The chance of it ever exceeding 50 ms (or whatever) is of about the same order as, say, lost clock interrupts or a hardware failure ruining your assumptions about the maximum local oscillator drift. Call the big delay a network "fault" and forget about it. The real advantage of multicast time is that you can update a large number of clients very frequently with next to no traffic. One minute updates can allow much greater precision under adverse conditions than, say, 15 minute updates in any case, yet the cost of serving 300 hundred clients this way drops from hundreds of packets per minute to one packet per minute. You may not care about this, since DTS often seems to me to be little concerned with accuracy in any case, but some people like it. And note that you've already allowed probabilities to creep into your inaccuracy interval by assuming one can configure a maximum drift for any system (of course, you punt on this by calling violations of the assumption "faults"), it seems to me that assumptions concerning one way delays across LANs do not increase the probability of the inaccuracy being wrong (and, of course, you can always call such cases "faults"). One comment about NCS and Kerberos for authentication. Authentication is notorious for increasing code path lengths (possibly asymmetrically) and this affects accuracy adversely. This is in part why NTP includes an integral authentication protocol, because it is concerned with accuracy and integrating the authentication allows it to optimally control the damage this does. Because NTP is concerned with accuracy (it is apparent that DTS is far less so) I can't ever see the internal cryto-checksum code being moved to an external agent (I would object if it was), since you can always do a better job, in the real time sense, with this incorporated as part of the protocol and coded by someone who is aware of the issues. NTP could use help with key management, though. Actually, upon rereading this note I find (in addition to it being far longer than it should be) that I've taken on to much of a pro-NTP debating tone. I apologize in advance. I guess the part that galled me is the "not willing to accept historical estimates of current network performance" comment as an excuse to ignore NTP's well developed, well tested time keeping technology when designing the DTS protocol, when what has really been done is to replace NTP's observation-based assumptions about the probability distributions of network gunk with assumptions concerning probabilities which have no basis in the real world and which are made strictly to avoid exposing a defect in DTS' representation of the inaccuracy. Dave's simulation results indicate that it is indeed the case that you've made DTS work worse in the real world than NTP (at keeping the clock correct, which is what I desire most from my time keeping protocol, not at computing correct error bounds, which I desire less anyway). NTP, with its current-reality based assumptions on network characteristics, couldn't do worse than DTS, whose assumptions seem based on nothing. Couple this with the stability and accuracy that NTP's local clock gives it (and the local clock is deterministic, the "historical estimates" fuzz can't even be used to justify ignoring this) and you've got a powerful, proven time keeping protocol. And DTS ignored all of it. Missing the local clock in particular is unforgiveable. NTP doesn't produce a "correct" inaccuracy, but there doesn't seem to me to be any reason which prevents it from doing so. The statistical assumptions it makes have no effect on this. If there are consumers who would like to know the inaccuracy (I would) I think NTP could provide it, perhaps without even changing packet format. And NTP doesn't have an autoconfiguration protocol, but it has wide experience with people- configuration and you couldn't possible design an auto-configuration protocol which does worse than people. I am sorry for the tone of this, but I can't help but take issue to the (apparent in DTS' design) attitude that nothing in NTP was worth looking at (from my perspective DTS' treatment of the local clock is horrendously primitive and simple minded, for example). I understand from your last note, however, that you are maybe growing more sensitive to this. If we are to standardize a time protocol, let us make it a good one by not ignoring existing experience. ------------------------------------------------------------------------ 24-MAR-1990 19:15:29.73 From: Michael Soha LKG1-2/A19 226-7658 To: comuzzi@took.dec.com CC: Mills@udel.edu, elb@mwunix.mitre.org, marcus@osf.org Subj: Re: More discussion of the differences (and similarities) of DTS and NTP. I realize that, while the NTP local clock processing is not a particularly difficult coding exercise, it rests on a foundation which is the subject of lots of textbooks and quite a number of academic journals. I also realize the presentation in Appendix F of the current NTP document certainly does not derive this stuff from first principles, since that would require turning the NTP spec into another control theory textbook. I can understand the derivation in there (though I couldn't have produced it, and could verify it only with great difficulty) by virtue of a somewhat academic, traditional engineering background (Dave seems to have a very academic, traditional engineering background), but I realize the stuff may look more than a little opague if no one has ever forced you to learn/use that stuff. It is, however, very worth while to get a handle on what is in there, at least functionally, because this can make orders of magnitude difference in the results you get from your time protocol. If the author is referring to Control Theory I agree that it is the subject of many textbooks and journal articles. However, if he's alluding to the modeling of quartz oscillators and their stability I have to disagree. My references, [2-6], do not use the model employed by NTP. Refer to my initial discussion on training. Aside, my NTP documentation, RFC 1119, does not have an Appendix F. I assume the author is referring to Section 5, 'Local Clocks' [Ref 1]. Speaking for myself, I took several courses in Control Theory, not so much because I was "forced", but simply because I enjoyed the subject. Let me a number of assertions, some of which I'm not going to be able to support here, but which can be discovered by looking very carefully at the local clock description. I think you will find that it is not what you think. (1) The NTP local clock does for NTP (and potentially for DTS) what adjtime() does for DTS. It is essentially a procedure which is called with a time offset as an argument, and which does something to the system clock as a result. I agree. Both NTP and DTSS are time synchronization protocols. (2) Like adjtime(), the NTP local clock is fully deterministic. There are no probability considerations here. When you give it a time offset, the effect this has on the system clock is fully predictable. Hence the NTP local clock can have no effect on your ability to maintain correctness, any more than the behaviour of adjtime() has any effect on your ability to maintain correctness. The NTP local clock does what it is told, no more and no less. Deterministic systems can be wrong. I don't think Joe was trying trying to say that NTP is indeterministic (God doesn't play dice with NTP). I think what he reacting to was the lack of a correctness proof and a definition for correctness. As discussed previously, I believe the NTP clock model is unsound. (3) I think the specified NTP local clock is (should be, I have to trust Dave's math for this) unconditionally stable for all input. Note that "stable" in this context has a very specific meaning, and may not be what you expect. If the NTP local clock wasn't unconditionally stable for all input with its current parameters, it could be made that way by adjusting those parameters. The stability of the local clock is predictable. Reading this paragraph I see the author saying NTP should be stable and if it isn't we can fix it. Referring to 'Modern Control Engineering' by Ogata [Ref 10], pg 7 "From the point of view of stability, the open loop control system is easier to build since stability is not a major problem. On the other hand, stability is always a major problem in the closed loop system since it may tend to overcorrect errors which cause oscillations of constant or changing amplitude". My interpretation of stability is just that, no oscillations. See Ogata, pg 217 'Absolute stability, relative stability, and steady state error' for additional discussion. Furthermore, while we are on the topic of stability, one has to acknowledge that a type II system is more apt to be unstable than a type I system. Again from Ogata, pg 284, "As the type number is increased, accuracy is improved; however, increasing the type number aggravates the stability problem. A compromise between steady state accuracy and relative stability is always necessary". There are no easy answers in this world. Is the NTP clock model the proper choice in terms of accuracy and relative stability? In summary, I agree with only one of Dennis' assertions, NTP and DTSS are designed to synchronize clocks in a computer network. The local clock, in both NTP and DTS, takes time offsets from UTC as input and attempts to adjust the system clock in response to these, in principle to make the offsets smaller. Note that this is a feedback loop, the the adjustments which are made to the system clock affect the next offset which is input to the local clock. Now suppose a DTS client has a clock which drifts by 100 ppm. Suppose it also manages to obtain offsets every 15 minutes, by exchanges with its servers, which represent the difference between the client's system clock and UTC accurately to the nanosecond. The client gives an offset to the DTS local clock, essentially adjtime(), which slews the clock by the amount of the offset, and then sits around waiting for the next offset to arrive. Of course, while adjtime() is slewing the clock towards 0 offset, the clock's drift is slewing it away at a rate of 90 ms per 15 minutes. At the end of fifteen minutes the whole thing will be repeated. Also, as adjtime() will typically slew the clock at a much greater rate than 100 ppm, the system clock offset from UTC will show a sawtooth waveform varying between 0 and 90 ms with a period of 15 minutes, and will average 45 ms off. So, for absolutely perfect data in, the DTS local clock can get the system clock no closer than 45+-45 ms. This is inaccurate (it isn't even meaningful to say that you are getting perfect data in, either, since the jitter will be fed back as an uncertainty in the input). Indeed, this inaccuracy is not unexpected. This is what is called a Type I feedback loop (I think), and is known to be unable to track an input without introducing a phase error on the output. Worse, for perfect data in consumers of time on that machine will see an uncertainty of +-90 ms, even though the true uncertainty is only half that (0 to 90 ms), and even though the input data is perfect. This is gross. I agree that if one has a very poor oscillator, it will drift on the order of 90 msec/15 minutes. However, before I apply the NTP clock model and expect to drive the stability to one part in 10**8, I'd first consider what is actually possible (ie, technically sound). Another aside, the statement "..UTC accurately to the nanosecond" is meaningless for several reasons. First, the current state of art for time transfer (using the Global Positioning System, GPS) can achieve a precision of a few nanoseconds Ref [5,8]. This precision is achieved through the use of cesium clocks, very precise position information, and long integration times. It is unreasonably, to say the least, that one could expect to achieve this precision in a computer network. Secondly, the use of UTC (as defined by the CCIR, Ref 9) states that '... UTC enables events to be determined with an uncertainty of 1 us;'. If you are looking at time transfer with a precision on the order of nanoseconds, one must specify Timing Center eg, UTC(NIST) (see Ref 11 for a description). The term Type I feedback is a reference to the steady state error characteristics for a control system. Saying that a Type I is unable to track an input without without error is wrong (see Ref 10 ppg 283-292) A Type I system can track a step input with ZERO steady-state error. For ramp input it will a finite error, which can be reduced by tailoring the 7** system. A Type II system can track a ramp input with zero steady 7** state error. As discussed earlier in response '5**' a proper solution is 7** always a compromise between several parameters (eg, stability, steady 7** state error, transient errors, over-shoot, time to first zero, etc...) 7** In other words, a type II system isn't always better than a type I. The NTP local clock does much, much better, by a couple of techniques. First, the jitter the DTS system clock experiences is essentially eliminated by not feeding an entire adjustment to the system clock all at once, but rather by making very small adjustments at frequent intervals (currently 4 seconds in the spec). The NTP local clock hence avoids introducing the sawtooth, the clock changes slowly and smoothly. Further, the NTP local clock corrects the average error by computing and applying a correction for the drift, by implementing a Type II feedback loop. Essentially, for perfect data in, the NTP local clock will eventually determine the drift of the system clock and, when it does, will maintain the average offset of the system clock at 0. I.e., perfectly accurate. A Type II feedback loop will track a fixed input accurately. By applying many little corrections to the system clock instead of one big one, NTP will also maintain the system clock relatively jitter free (one could say absolutely jitter free in comparison to DTS). For perfect data in, the NTP local clock MODEL may be able to reduce the offest to zero. However, as for the actual quartz oscillator, it impossible. There will always be short-term drift, as discussed in the beginning of this memo. As for, Type II vs Type I, it is naive to say that a Type II system is always better than a Type I. What is better? less stable? more accurate? more transient errors? Of course, there is no such thing as perfect, but we can begin to assign relative orders of magnitude to errors of the DTS and NTP local clock schemes (this comparison is deterministic as well, there are no probabilities involved). DTS' local clock error is proportional to the drift. NTP's local clock error is proportional to the rate of change of the drift with respect to time multiplied by the time constant of the PLL. In the real world the latter is less than the former by at least several orders of magnitude. It is wrong to say that: DTS' local clock error is proportional to to drift. The inaccuracy will grow at a rate equal to the maximum drift. The test data to date indicates that most VAX oscillator are much better than 1 part in 10**4. So the difference between two DTS local clocks will be much better than the max drift. So why use 1 part in 10**4, that number accounts for all expected drift components: initial offset; aging for the lifetime of the product, 10 years; and environment (temperature, humidity, voltage supply, etc). I have a real problem with the quote 'several orders of magnitude'. I have seen in several discussions on NTP that it can achieve stabilities on the order of 1 part in 10**8. All of the data that I have seen on quartz oscillators [Ref 2-7] indicate that is impossible for uncompensated oscillators to reach a stability of one part in 10**8. I have grossly oversimplified this, but please believe that the details are all in the NTP spec if you decode them. Now, how can replacing DTS' use of adjtime() with something which is more accurate affect DTS' configurability? How could it possibly affect correctness? I stand by my original statement, that the issue of accuracy (with respect to the local clock) is completely and utterly orthogonal to any issues of configuration or management. DTS just didn't include the machinery to condition with the local clock (and apparently is hung up on type I feedback loops for clock control when there are other better ways to do it), and this is what is so frustrating about it. If one adds complexity to increase the accuracy of a system, than it may result in additional management and/or configurability. In fact I'd argue that this is true more often than not. Saying the two are completely and utterly orthogonal is overstating your case. Personally I like control theory, mainly because it is a challenge to do the right thing. The question of Type I vs Type II is (for me at least) unrelated to why I don't like the NTP clock model. I simply believe that it is technically unsound to 'train' an uncompensated 12** oscillator [Ref 2-6]. I also think your claim that using local clock processing which does frequency compensation would require one to *increase* the inaccuracy must either be wrong, or indicate that DTS is doing something very silly. Does it make sense that something which can be analytically shown to increase accuracy increases the inaccuracy? Does it make sense that, if I tune a crystal for zero drift in hardware with a screwdriver that the inaccuracy should decrease, while if I tune it for zero drift in software the inaccuracy must increase? The mind boggles. The reason you may want to consider increase the inaccuracy is for robustness. That is, if the correction is correct 99% of the time, then for the 1% of the time that the correction is incorrect, you will still contain UTC in the time interval. Further, I think you may still be operating in an unreal world with the assertion that a manufacturer could possibly define a maximum drift for the clock in a particular model of machines, one that could never be exceeded under any circumstances which couldn't be called hardware failure. I would suggest to you that the very worst cause of clock drift in real systems is not hardware at all, but rather lost clock interrupts (which cause large, negative drifts). Would you be willing to certify that DEC hardware/operating systems never lose clock interrupts under any circumstances? Or provide a guaranteed limit to the number that will be lost in any time interval? You can call lost clock interrupts a "fault" if you wish, but implying that such "faults" are "historically" a rare occurrence flies in the face of experience, at least with Unix systems. Stating a maximum number for drift can be done if one accounts for all of the contributors to drift (short and long term). One only needs to examine the oscillator specification. The main contributors are: aging, initial accuracy and temperature stability. Accounting for these contributors one can easily show that a stability of 1 part in 10**4 is a proper choice (assuming a lifetime 10 years). I agree that accounting for missing clock interrupts is a very difficult problem. Does NTP have a solution for this? Which brings up another assertion I am beginning to doubt, that NTP does not (or cannot) know the inaccuracy of its time estimate. Joe, take a look at how NTP's synchronization distance is accumulated. Don't worry about the value of this that the spec suggests be used for stratum 1 servers, let's assume that this is configured for stratum 1 servers in a way which agrees with DTS. Look carefully at how the synchronization distance a stratum 3 server will receive. Do you see any reason why I could not assert that UTC must be contained in an interval which is +-1/2 the synchronization distance from the system clock's time, and prove this assertion by the same principles that DTS uses? Or, if not, that there are any uncorrectable imperfections in this assertion? I agree that NTP may be able to provide an inaccuracy. But you may need additional data to account for processing delays and the local clock resolution for each NTP node from the stratum 1 server. The question becomes, then, what is all that statistical junk that NTP does? I think the issue that is being missed here (and I'm on thin ice again) is that DTS does indeed make some assumptions about probability distributions. In particular, all correctness can give you is an interval which should include UTC. The system clock, however, cannot be set to an interval, it needs a specific value. DTS hence arbitrarily assumes that any time in the interval are equally likely to be UTC as any other, and hence picks the middle of the interval as this minimizes the probable error based on that assumption (the fact that not picking the middle of the interval increases the inaccuracy interval demonstrates a flaw in the DTS protocol which is also exercised by the local clock processing. The protocol demands that the intervals be +-something even when it might be known that the true interval is +something -something- different. DTS hence claims inaccuracy intervals which are often bigger than the? should be simply because it lacks the ability to represent the true state of affairs. This doesn't affect correctness, but reduces the utility of knowing the inaccuracy interval). See my response [above] and my initial discussion on training. DTS is not optimal since it balances the inaccuracy about the midpoint. One need not use a balance interval by providing three datapoints: time, +inacc, and -inacc; however we decided that this optimization was beyond the point of diminishing returns. NTP, however, assumes that the probability distribution over the interval is non-uniform, that some times within the interval are more likely to be UTC than others (this isn't strictly true, but I see no reason why it couldn't be). It proceeds to determine the time within the interval which is most likely to be UTC and sets the clock to that. NTP does this in part by casting off samples and servers which it thinks are less reliable. If DTS can correctly synchronize to a single server, however, then casting off servers you aren't fond of can't affect correctness. NTP choses servers it likes (and samples from servers it likes) based on presumed characteristics of the probability distributions of network traffic. This has no effect on correctness, however, and in the extremely unlikely event that the network does not behave in the way that NTP expects, NTP's choice of UTC will probably be no worse than DTS'. This has no effect on NTP's ability (or lack thereof) to produce correct bounds on the estimate, in DTS' sense. Also, I find it strange that DTS could claim that avoiding having to "accept historical estimates of current network performance" is a feature, when this is done by making assumptions bout probability distributions which have no basis in practical reality at all. 'most likely to be UTC' describes why NTP is different form DTSS. NTP focuses on accuracy while DTSS main goal is to always include UTC in the computed time interval. Neither one is necessarily better than the other. As described in Dennis' memo and my responses, NTP uses a different control mechanism than DTS (eg type II vs Type I). Given this, it is difficult to accept the claim that NTP choice will be no worse than DTSS'. Two points. 1. Historical estimates of network performance may be stale due to changes in the network layer (different routes) and the datalink layer (changes in the bridge topology). How does one ensure that the network performance estimates reflect the current state of the affairs. 2. The statement the 'DTS's assumption have no basis in reality' is false. See response **14 and my initial discussion on reality. A couple of things come to mind. Joe, you mentioned something about "wild instabilities" which Dave said NTP might suffer in the face of poor server selection, or some such. I would suggest to you that the term "wild instabilities" is one which is relevant only in relation to one's expectation of the performance of your time protocol. To anyone who thinks an error of 45+-45 ms in the time the system clock returns when given perfect data is acceptable, NTP is as solid as a rock. NTP's "wild instabilites" are only relevant if your expectations are much higher than DTS', since "wild" for NTP is a lot smaller than the instabilities DTS apparently considers normal. I thought this comment originally came from Dave (wrt DTSS giving time to NTP). It may have been overstated, however the point remains that it is more difficult to ensure stability in a Type II system (as compared to a type I). More than this, I fail to understand the rest of the arguments about why NTP couldn't be retrofitted with an autoconfiguration protocol. NTP has no configuration rules, it places itself in the heirarchy based on the servers available to it. NTP will operate in such a way as to maximize the probable accuracy of its time no matter how it is configured. Give your NTP daemon a random set of peers and it will chose the best of them, adopt a stratum which is appropriate based on the time sources available, and make the best use of the time available. Concerns about "phase noise" (i.e. jitter) are again based on expectations of the performance of the time protocol, an NTP server which takes time from your 45+-45 ms host will survive just fine, and indeed will show far less jitter than +-45 ms (look at the local clock, high frequency noise is damped out). It is just that NTP servers are expected to be a lot closer than 45 ms, so your host looks bad compared to NTP's expectations (but not needs). Further, the stuff about synchonization loops is irrelevant. The NTP protocol survives loops just fine, it's just that the consequence of a loop is that the machines involved count their statum to infinity and disconnect from the synchronization subnet rather than continuing to fool themselves that their servers know something they don't. This is quite reasonable behaviour since NTP clocks don't drift much when left unsynchronized. I would suggest to you that NTP knows far more about Murphy than DTS does at this point, since it has been tested in far more environments, on far more machines, in likely far harsher environments, through far more revisions, for far longer than DTS has. There are three independently done implementations of NTP, all of which work well and interoperate. How complex can NTP be? NTP can be given a random set of servers and work just fine, thanks. This wasn't done with auto-configuration specifically in mind, but rather simply to meet robustness requirements. NTP has a lot of real world experience to prove that it is robust, and that it is certainly robust in the face of even gross misconfiguration. What more is needed for an auto- configurable protocol? Autoconfiguration certainly couldn't do a worse job than people do. As for Byzantine failures, you are right that NTP's scheme for leap second notifications suffers from this, but what is the worst thing that can happen if this occurs? Right, your clock ends up a second off. With DTS, however, it is a virtual certainty that the clock wil end up a second off when a leap second occurs, so criticizing NTP for leaving this hole is a little like the pot calling the kettle black. That DTS increases its inaccuracy by a second is irrelevant for comparison, since NTP doesn't maintain this inaccuracy. If (when) NTP maintains an inaccuracy interval it should probably increase it by a second during leaps as well. This doesn't help keep your clock accurate across leaps, though. The statement that 'NTP should increase it's inaccuracy' implies that DTSS is doing the right thing. Am I confused? For broadcast time, however, I think this is incorrect. The NTP clock selection code includes an agreement protocol, and this is still used for broadcast time. To cause a failure one would have to co-opt a majority of the servers, and this is hardly less robust than DTS. I can see little more exposure to such failures with broadcast time than with polled time, and I think we must agree that polled NTP is not less robust in the face of Byzantine failures than DTS. Further, if you are really worried about hostile attacks on your clients then you'll be using authentication anyway, in which case there is no additional exposure to such failures. More than this, note that NTP's multicast time is used in the LAN environment. The transit delays here are a few milliseconds, and indeed my daemon includes partially implemented code to determine these delays on the fly by polling. This transit delay isn't even measureable by a lot of machines (between machines with 10 or 20 ms clocks you end up computing absurdities like negative round trip delays. Does DTS handle this?), so DTS isn't necessarily going to know a whole lot about this delay by polling anyway. Now, you are willing to accept a 45+-45 ms error in the setting of your clock and a 90 ms inaccuracy, for perfect data in, due to the primitive local clock processing that DTS does, why the heck not add in another, say, 50 ms or something equally outrageous, to the inaccuracy interval for the broadcast and forget about it? The chance of it ever exceeding 50 ms (or whatever) is of about the same order as, say, lost clock interrupts or a hardware failure ruining your assumptions about the maximum local oscillator drift. Call the big delay a network "fault" and forget about it. How do you account for changes in the bridged LAN and/or remote bridges. Most LANs or bridged, a change in topology will affect the network delay. Furthermore, if one has a remote bridge, say at 56 kbps, then for each minimum size packet (64 bytes) another 5 msec of ONEWAY delay (ie, asymmetrical) will be introduced. We have measured ONEWAY delays on LANs (with only local bridges) as high as 100 msec. As discussed in previous comments I do not agree that NTP will work the same as DTSS. As for the local clock, I do not believe that it is technically sound to 'train' an uncompensated clock (see discussion on training at beginning of this memo.) I am sorry for the tone of this, but I can't help but take issue to the (apparent in DTS' design) attitude that nothing in NTP was worth looking at (from my perspective DTS' treatment of the local clock is horrendously primitive and simple minded, for example). I understand from your last note, however, that you are maybe growing more sensitive to this. If we are to standardize a time protocol, let us make it a good one by not ignoring existing experience. To be frank, I would say that NTP's view that an uncompensated can be 'trained' to one part in 10**8 has no foundation in the scientific literature. REFERENCES 1. Mills, D. L., "Network Time Protocol (Version 2) Specification and Implementation", RFC: 119, University of Delaware, September 1989 2. Vig, J. R., "Quartz Crystal Resonators & Oscillators For Frequency Control and Timing Applications", SLCET-TR-88-1,US Army Electronics Technology and Devices Laboratory, Fort Momouth, New Jersey, January 1988. 3. Bottom, V. E., "Introduction to quartz Crystal Unit Design", Van Nostrand Reinhold Electrical/Computer Science and Engineering Series, New York, 1982 4. Frerking. M. E., "Crystal Oscillator Design and Temperature Compensation", Van Nostrand Reinhold Company/Litton Educational Publishing, 1978 5. NIST, "Time and Frequency Seminar - June 14, 15, 16 1988" Time and Frequency Division, NIST, Boulder Colorado 6. NIST, "Time and Frequency: Theory and Fundamentals", NBS Monograph 140, SD Catalog No. C13.44:140., Boulder, Colorado. 7. VECTRON, "Crystal Oscillators 1989", VECTRON Laboratories, Inc, Norwalk Connecticut. 8. Imae, M. et al, "A dual frequency GPS receiver measuring ionspheric effects without code demodulation and its application to time comparisons", Proceedings of the 20th Annual Precise Time and Time Interval (PTTI) Applications and planning Meeting, Vienna, Virgina, 1988. 9. CCIR, "Recommendations and Reports of the CCIR, 1986 - Standard Frequencies and Time Signals", XVIth Plenary, Dubrovnik, 1986. 10. Ogata, K., "Modern Control Enginnering", Prentice Hall Inc, Englewood Cliffs, New Jersey, 1970. 11. NIST, "Time & Frequency Bulletin No. 388 March 1900", NISTR 90- 3940-3 (a monthly report from NIST), Time and Frequency Division, NIST, Boulder, Colorado. ------------------------------------------------------------------------ Date Tue, 27 Mar 90 4:59:06 GMT From Mills@udel.edu To comuzzi@took.enet.dec.com cc mills@udel.edu, dennis@gw.ccie.utoronto.ca Subject? Re? I've sent this to everyone else, yours bounced because of a typo. ... This is a note to continue the DTS/NTP comparison, because I too am finding this conversation fruitful. Dennis, I would be glad to mail you a copy of the DTS architecture if you want one. (and Dave, I've even changed the cover and introduction). ... Yeah, I've learned something, too. Are you game to cast the document as an RFC? It's too bad we didn't schmooze while the stove was still simmering the kettle. Is the kettle still warm? ... Allow me to start with the decision of DTS not to support a multicast mode. One reason was that protocols which multicast the time will be subject to Byzantine failures. ... There are two issues here, one pragmatic and the other hidden. Since NTP multicast clients may enjoy multiple NTP multicast servers on the same wire, Byzantine vulnerabilities are reduced. The only thing you lose is the synchronization delay (aka inaccuracy interval - darn, we should have both called that the "confidence interval"), which in Unix community is imperceptable. The hidden agenda is to explore the utility of the new IP multicast capability, which is quickly becoming ubiquitous in the Internet R&D community. While I would like to make the case that multicasting should be supported on its own merits, I have great nervousness about such scenarios as CMU, which as you probably know, runs what could be called a godzilla network of intertwined wires and bridges. I am told that each of several NTP servers now hark upwards of 500 clients each. If each one of those clients dudes expects to rattle chimes of, say, three servers each, the induced RF field might misdirect planes 50 miles away. ... The second point, the one I was trying to raise in my reply to Dave, was that it was DTS's intention to have the time and interval information available on every node. The inaccuracy interval is available in NTP, too, but a Unix interface is not. While not specified in the NTP spec, a clamp should be placed on the frequency compensation term, like +-20 ppm or something like that. It would then be possible to make almost the same confidence statements about NTP as for DTS. The "almost" is because of the basic difference between the NTP selection/combining algorithm and the DTS intersection algorithm. These issues need to be discussed at another time. ... The third point I'd like to discuss refers to Dave's statement about a "considerable Internet constituency which has noisily articulated the need for a multicast function when the number of clients on the wire climbs to the hundreds." Is it that they wanted multicast? Or was the real objection the practical difficulty of adding a second server to a LAN of 300 nodes and then having to change the server entry in 150 ntp.conf files to redistribute the load? ... The quote is quite correct. A number of dudes jumped on me to include multicasting in the spec. Their perception is more concerned with network load than with correctnes; however, I readily admit they might not have yet become sensitive to the configuration issues you raise. However, I continue to believe the autoconfiguration issue transcends NTP and should be considered in a wider context. ... The next topic I'll discuss is the area of the DTS architecture I personally believe is least likely to survive the standardization process unchanged: The timestamp format. I think we have much agreement here. I still have a few scars left from old Internet wars on this point, including the use of binary versus character-oriented formats and whether leap seconds are meaningful. The fact that leap seconds cannot be reliably predicted seems to be a showstopper. As long as you must have institutional memory for them, it may be easiest to include epoch era information using the same mechanism. ... There has been a fair amount of discussion about interoperation of the two time services. Let me try to clarify what I said (too tersely) in my original response to Dave's paper. There are three separate cases I'd like to distinguish A) An isolated group of DTS systems which obtain time from NTP B) An isolated group of NTP systems which obtain time from DTS. C) A collection of DTS and NTP giving time to each other. I believe that without fairly major changes in one or both of the architectures case C is a problem, however it is an easily prevented problem (see below). Cases A and B however are very interesting, useful and I claim easily achievable. I see no problem with A and B either, even to the point of equating synchronization distance to inaccuracy interval. NTP would have to assign a stratum number to a DTS client and DTS might want to mark the synchronization distance provided by NTP as a "possibly unreliable inaccuracy interval." You have enough bits in the DTS timestamp to even do that, as well include leap warnings. I would even suggest amending the NTP spec to include such an interface specification and the DTS spec to include an identifier for the primary reference source. For this reason and in order to suppress neighbor loops, NTP includes the synchronization source in the header. ... Case C potentially breaks the invariants of both protocols. The DTS invariant is that UTC is contained within the interval. The NTP invariant (I'm less sure of my statement here) is that the frequency of good servers agree with UTC. In fact, the intent is to phase-lock all the clocks to UTC, which means both in frequency and time. This is not so much an invariant as a goal; although in practice it is achieved in much the same fashion as the power grid keeps your electric clocks humming UTC. Yeah, I tried that too and investigated whether the power grid itself makes a usable time/frequency transfer medium. Even though the guys in Columbus run the eastern-divide grid from a WWVB clock, local utilities drop off the grid from time to time and do not feel it necessary to maintain phase continuity, but that's another story among many other hilarities to be shared at another time. ... NTP has a further invariant, that there are no loops in the time distribution network. This is enforced by the stratum. Clearly if DTS took time from a collection of NTP servers and later gave it back to the same collection of servers, a loop could and probably would occur. There is a simple method to prevent this, I propose that the gateway described in case B above always declare itself to be at some fairly high (numerically large) stratum. Potential clients will ignore the DTS/NTP server in favor of servers which obtained their time exclusively via NTP (and have much lower stratum numbers). I'm assuming that the NTP implementation at the gateway can be coerced into using a fixed stratum and would propose a value of 16 for this purpose. This is a useful approach and requires only minor mods to the NTP spec. However, please don't underestimate the importance of the stratum, which is useful to avoid instabilities such as spurious clockhopping and loops. ... There's also a stratum zero which is supposed to be used when the stratum is unknown, however I'm not sure I understand what value servers which obtain their time from a stratum zero server will use. Do they use zero? If so, how are loops prevented amongst themselves? ... Stratum zero means "undefined," which can mean a lot of things, usually that the client has not yet synchronized. NTP peers will not synchronize to a stratum-zero peer, but will run the protocol so the peer can get synchronized. ... A few nits before we get to the meat of the discussion. Dennis is concerned that the drift has to be input as a management parameter. I'll show my vendor colors here and say this isn't a management parameter but an implementation detail. Dennis is not talking about the max frequency offset (I have problems with "drift," since in the communications field this means a change in frequency with time.), but with the estimated frequency offset produced by the local-clock algorithm, which is usually much lower. It can take an NTP peer some days to finetune the frequency, compliance and whatnot to produce stabilities in the .01-ppm range, so implementations can reduce the time to converge by remembering the offset and recovering it on reboot. The problem I have with arbitrary max's is that they are quartz-centric. You can certainly stamp the nameplate with the oscillator tolerance and expect it to be maintained throughout the service life of the equipment, but I sure wouldn't want to rely on the nameplate in our shop where machines are gloriously cannibalized and CPU boards routinely swapped. You could, of course, stash info like this in lithium along with the Ether address and license serial, but I doubt too many would take it seriously. Nevertheless, the same thing you say about DTS applies to NTP, assuming the clamp I mentioned previously is added to the frequency compensation. The nameplate would then specify the sum of the quartz tolerance plus the clamp. ... The second nit has to do with DTS's treatment of leap seconds. I appear not to have been clear here. Dave's original document was basically correct in its description of how DTS handles leap seconds - Servers increase their inaccuracy at the month boundary and a time provider narrows the interval later. When I wrote: "Each server has to maintain and propagate this state before the leap insertion. This is, of course, subject to Byzantine failures. A failing server can insert a bad notification." I was describing my understanding of (and a problem with) NTP's leap second handling. If my understanding of NTP is incorrect, I apologize, but the Byzantine problem seems real to me. I still am unsure how to incorporate a leap second into a prolific DTS subnet, if I can use the term. I assume all the DTS gizmos in the world will ramp up their inaccuracy intervals by one second at the end of every month. Let's say a leap second occurs and is eventually recognized by most of the radios (all extant radios sail right through a leap, only to lose synchronization later and then recover it). This takes a few minutes to a few hours. Servers and clerks will discover this fact from two to fifteen minutes later. While it is true that the inaccuracy interval will be correctly maintained, it may come as a shock to some users that for some uncertain period their timestamps suddenly took a one-second hit in accuracy. Assuming the time providers are told, either by radio or keyboard, that a leap is nigh, it would be possible to remove this ambiguity by stealing a bit in the timestamp format. ... Dave asked if I am in substantial agreement with the statistical models presented in his first document. I agree with most of this section. My only significant disagreement is with the last paragraph. It is true that DTS assumes that a system's clock drifts at a rate less than its manufacture's specification, and that a hardware time provider operates within specification. The probablities of these assumption being false are on the order of magnitude of other hardware failures. Software implementation do not routinely checksum memory any more (and they certainly don't do it to find memory errors). Violations of these assumptions represent faults, just as real as processor faults, and should be fixed. Note the long tails you observe in the distributions in the Internet are on message transmission times and the like. These parameters are dynamically measured in the DTS algorithm. Wick Nichols stated: "DTS is willing to accept historical estimates of the probability that a clock will go faulty (with checks for faultiness), but is not willing to accept historical estimates of current network characteristics." in his discussion of this point for the OSF. I'm struggling for a way to state my position in the most compact way I can, while still being fair to both the DTS and NTP models. I think we both agree that there is a tradeoff between accuracy and correctness. There will always be some tails in the error distributions for time providers, servers and network paths, as we have amply demonstrated over the years. Dennis' comments about missed clock interrupts are on the mark, as well as pragmatic mysteries on reading clocks in real operating systems. Your example of log coordination is a good one, as I have been using NTP for several years doing just that. However, in my battles with the old NSFNET Phase-I backbone, it was essential that transcontinental events (on the backbone) could be tagged accurately within ten milliseconds or so. Even today I expect NTP to correctly tag the Norwegian atomic clock to within half a second, in spite of gross misconduct across the Atlantic, as you may have seen. I thus see neither the statistical approach of NTP nor the correctness approach of DTS as necessarily "right," just different. I did a little experiment you might enjoy. Using the simulator mentioned previously and first the NTP and then the DTS selection algorithms, I purposely wiggled the offset of one of three clocks from nominal to a couple of seconds off, the idea being to create a falseticker in gradually increasing steps. The inaccuracy interval in both cases was calculated as in DTS, but without a time dependence, since the intervals between updates are small and the residual frequency offset is very small. While I hardly have enough data to make a definitive judgement, I can say that NTP quickly tossed out the bad clock, while DTS hung on for dear life rather longer than I would expect. I intend to play with this some more. My experiment pointed out a possibly noxious issue. I was at pains to make sure the inaccuracy interval was computed correctly, starting from the primary reference clocks that were in fact peers of the Norwegian chimer. However, the path is quite noisy, with effect the customer receiving the time-inaccuracy stamps can get wildly differing inaccuracy intervals on successive samples. It would seem the DTS customer would have to accumulate a number of samples if only to make sure the inaccuracy interval was reliable. In principle, this is the same strategy you suggest for time providers. I don't see anything necessarily wrong with this, but it does demonstrate that escape from probabilistic mechanics probably contradicts the third law of thermodynamics. ... Dennis asked a question about DTS authentication in the Internet environment. What I personally would like to see is an implementation of DTS using Apollo's NCS which in turn used Kerberos authentication. This is basically what Digital has proposed to the OSF in response to their distributed computing request for technology. My friends the electric spooks tell me Kerberos has real conceptual problems and that we should salute SNDS instead. Believe it when they tell us how to implement KMP and Firefly. Be advised it takes more than 100 ms to calculate the NTP cryptosum in an LSI-11/73 (yeah, I know I deserve that) and this cannot be compensated unless the protocol can measure and adjust the timestamps accordingly (my ISOfriends are much aggravated by that position). ... Now to the major contention of Dennis's review, that accuracy and ease-of-management are "completely and utterly orthogonal". I disagree with this less then a reader of my response to Dave might think, though I am somewhat in disagreement with it. What I hold is that ease-of-management, provablility and accuracy for a time service are all interrelated. Those guys who actually do mount and run large NTP subsubnets (Merit runs 150 chimers in the NSFNET backbone alone, most of which have identical configuration files) can speak eloquently about their own hardships. That's not to say I don't believe you, just that others should make the NTP case. ... The problem with just adding the NTP local clock model to DTS (as I understand the NTP local clock model) is that the resulting system could have wild instabilities. (Maybe my understanding of NTP is incorrect here.) The dynamic nature of the DTS autoconfiguration rules (couriers choosing a random member of the global set for instance) means the the input time driving the local clock model will have what Dave calls "phase noise". As I understand NTP's local clock model this is where the instability creeps in. It's not so much the phase noise as it is the dynamics of the local clock loop itself, sort of like requiring tickadj to have a confined range of adjustment. The rate at which the loop corrects for time and frequency errors is fundamental to its stability; otherwise, it could surge in much the same fashion as if you tried to drive a car with a half-second delay between the steering wheel and the steered wheels. I believe, as I hope is demonstrated in NTP implementations, that appropriate parameters can be specified and engineered for any implementation, either DTS or NTP in much the same way that tickadj is engineered now, even on an optional (configured) basis. I envision a local-clock implementation appropriate for either NTP or DTS or TSP for that matter by selecting either model with engineered parameters determined only on the basis of whether you have a line-frequency oscillator, an uncompensated quartz oscillator or a GPS receiver or atomic clock. This is in fact the fuzzball implementation. ... Further, the existing NTP protocol avoids loops by using a stratum concept, again the DTS autoconfiguration happily produces loops. As I noted previously this doesn't effect the DTS algorithm, but they would cause havoc for NTP. Again one could add complexity to the DTS algorithm to prevent the loops, but I claim one would pay a price in system management cost. I perceive the DTS model does not consider more than three "strata" (global server, local server, clerk) necessary in a DTS subnet, right? If this can be assured, NTP is in fact needlessly complex. However, we are not building NTP subnets this way and have found it necessary to use a richer hierarchy requiring more strata, even if some LANs have their own time providers. One reason for this is a notorious distrust of time providers, so all NTP primary servers chime (usually at least three) other servers, not even necessarily primary servers. Also, even in this university, which is hardly at a loss for time providers (!) we have many stratum 4 and probably stratum 5 chimers even now. ... Another problem (according to Dave) is that the resultant phase locked loops have to be analyzed in the light of assumed probability distributions, etc. and one does not end up with the sort of proofs of correctness that are what is liked in DTS. There is one interesting aside on this last point. I believe there is a way one could add clock training to the DTS model and preserve the correctness. If the training algorithm decides to change the rate of the clock by some amount, *increase* the maximum drift rate by that amount. I believe this can be shown provably correct by the techniques in Marzullo's thesis. However, while this improves the precision of the time (the intersystem phase differences and rate differences will be smaller) the inaccuracy (the guarantee given to the user) will be worse! That DTS has chosen not to do this is, of course, the basic philosophical difference about what's important showing up again. However, the existance of at least one method to incorporate clock training into a provable system gives hope that both camps can be satified and in particular that the large body of work on the NTP local clock model can be incorporated. I am not (yet) expert enough in the NTP local clock model to see my way through this. While it may be that the inaccuracy interval provided to users may degrade slightly if frequency compensation is embraced, the inaccuracy jiggles certainly can't be as bad as the rock-n'-roll I see with the simulator and Norway data. I sense there is room to jostle on this issue. ... The other obvious possibility is to just add the autoconfiguration to NTP. To an extent, this is occuring. The multicast functionallity clearly addreses the ease-of-management issue. However, for NTP servers, I claim that chosing the right server is important enough that it can't be left to an algorithm. Swithing at random between servers reintroduces the clock-hopping problem (the the extra phase noise produced by the clock-hopping will cause problems for NTP.) One could attempt to just pick a set of server at random and stick with them for some long time to reduce clock hopping, but that will produce serious sub-optimality in the case of a changing network configuration (The particular servers being synchronized with might become cut-off from their good time sources, or the paths to them might involve links which become overloaded, and this wouldn't be discovered for a long time.) The reason for the NTP selection algorithm is to find the "best" clocks from a population possibly including "poor" ones on the basis of estimated accuracy, stability and so forth. The selection and weighting factors are dynamically determined using what I hope are sound statistical principles and are considered so important that only a purpose-designed algorithm could do it, much less an autoconfiguration scheme. I think what you have in mind are discovery and configuration issues, which certainly could be improved were DTS algorithms to be mimiced. Do you hear a faint echo of the old Xerox Clearinghouse in the far distance? ------------------------------------------------------------------------ Date: Fri, 30 Mar 90 08:30:48 PST From: comuzzi@took.enet.dec.com To: mail11: ;, "@dts-ntp.dis" Subject: More discussion of NTP and DTS Dennis, Sorry for the delay in responding, I wanted to review where we are and try and summarize our positions. It happens that I'm not an expert in control theory. Mike Soha, who is a student of that subject has already responded to your discussion. I look forward to a continued lively exchange. Dave, You've asked this question twice (whether DTS will appear as an Internet RFC) and it deserves an answer. It turns out that about three or four months ago Ross Callon tried to elicit interest in DTS in the Internet Engineering Steering Group (of which he is a member). Ross wanted to submit an RFC, but The response was not encouraging, basically he was told nobody wanted to think about time services. I agree with your observation that it would have been better to have these conversations earlier. I'm assuming the ISEG's lack of interest will change if OSF selects DTS as one of its Distributed Computing Environment technologies. If that happens however, the architecture specification will probably be tweaked to reflect other OSF technology selections, such as which nameservice, RPC, etc., but we will submit an RFC. Even if DTS is not selected, I believe it would still be a good idea for DTS to appear as an RFC (I suspect the relevent powers would entertain a DTS RFC if you supported it). Now continuing the discussion, Dave's observation that DTS is not dead- set against clock training is in fact correct. Clock training can be viewed as orthogonal to the DTS architecture, though of course any training would have to be done in a way which preserved the Marzullo proofs. Mike describes in his note a simple proposal he has for incorporating clock training. The question I have personally been struggling with, and haven't had much success understanding is: In the furture, if DTS incorporated the NTP local clock model how much of the rest of NTP would have to come along with it? In particular, would the various fields in the time response message (e.g., synchronizing dispersion) be required? (It seems that these have more to do with the clock selection algorithm) Are strata required, or is the loop breaking mechanism of inaccuracy (synchronization distance) sufficient? Can the local clock model be proven to be stable for all input? Earlier, I got the impression that this could only be done by making rather strong assumptions about the network distribution functions, etc. Now I'm not at all sure of that, based on recent statements from Dave and Dennis. I hope this will fall out of the continuing 'control theory' discussion. Dave correctly observes that the DTS architecture only has a three level hierarchy. The DTS architecture has been extended (as part of the OSF submission) to permit the specification of a local set which is not autoconfigured. Basically, the local set is enumerated in a nameservice directory just like the global set. This permits construction of a hierarchy in which one level's global set is another level's local set. Obviously this is only autoconfiguring at the leaves, but it does permit construction of as complex a hierarchy as one would desire. We are *NOT* going to tell customers to do this, and the vast majority of customers will be quite content never thinking about strata or multi-level hierarchies. The real difference of opinion here is whether the majority of extended LANs will have their own time providers. DTS assumes that TPs are becoming commonplace. In that case, one only does WAN transactions as a check for inter-XLAN time differences, and to support small (TPless) LANs. For this environment, the short hierarchy suffices. Thinking about the "autoconfiguration vs. accuracy" issue in light of the the different TP availablity assumptions, I believe I understand the disagreement. (I think Dennis had figured this out too, I just hadn't read what he was saying!) DTS derives much of its ease-of-management because it only thinks in terms of a three level hierarchy, it autoconfigures the leaves, and it uses a single global set stored in the namespace. If NTP was used in a similar manner, then NTP could be made equally autoconfiguring. I agree. The point I was trying to push is that when you create a new server for NTP, you have to figure out where to put it in the grand hierarchy and further you have to select peers for it that will provide reasonable quality time. Now if you don't have an NTP hierarchy, then my argument is specious -- the same strategy that works for DTS would work for NTP. To summarize (I believe) Dennis' position: NTP can be made just as autoconfiguring as DTS. Indeed it already has some of the autoconfiguration due to its multicast mode; it just needs the discovery mechanism. The result would be more accurate than DTS, due to clock training. My position would reduce to: DTS is a simpler protocol which already has the autoconfiguration and could be made more accurate by adding some clock training. These positions are not that far apart. There is still a remaining disagreement: how much clock training or other complexity to add and what the optimal amount of complexity is from a cost-benefit analysis. Now, as I understand Dave on the autocofiguration issue, his position is: TPs are not (and will not become in the near future) that commonplace, so more than a three level hierarchy is required. Hence only the leaves can be made autoconfiguring and there will always be some residual manual configuration. (I'm looking for an agreement on what our various position are here, I am willing to accept that we disagree for now.) Considering the larger question of "manageability vs accuracy" there is still a lot of complexity in NTP which manifests itself as more management complexity. I observe there are at least three parameters (associated with the filter and selection algorithms) whose description includes the sentence "While the value of ... is suggested, the value may be changed to suit local conditions on particular peer paths" (or similar text). This seems to me a rather frank admission of more management (as opposed to more work for implementors). We seem to have no agreement (due to our different goals of how much accuracy to deliver in the first place) on these trade-offs. I believe there two issues where we have reached complete agreement: Both Dave and Dennis seem to be in agreement that NTP can be modified to include a provable inaccuracy bound, equivalent to DTS's inaccuracy. (I'll stick to the DTS jargon because I'm more comfortable with it. Dave's term confidence interval is a reasonable name.) This interval could be provided to the end user. I believe this also. I hope that NTP will continue to evolve in this direction, independent of the OSF decision. Second, I believe we are in agreement on how (adequate) interoperation between the protocols could be achieved. I'll sign-up to discuss this in the DTS RFC. I am curious about Dave's experiments with the DTS algorithm. Dave, can you provide more details (possibly out-of-band to this discussion)? This note is already longer than I intended, so I'll send it out. I'll keep the discussion of layering a time service over an authenticator (that Bill raised) for later. ------------------------------------------------------------------------ Date: Mon, 2 Apr 90 10:00:22 PDT From: Michael Soha LKG1-2/A19 226-7658 To: dennis@gw.ccie.utoronto.ca Cc: decpa::"Mills@udel.edu", decpa::"elb@mwunix.mitre.org", decpa::"marcus@osf.org", soha Subject: My response to Dennis Ferguson's NTP vs DTSS memo - retry Dennis, When I first read this memo, I discounted it as part of an emotional discussion of why NTP is the right choice. However upon reflection I felt it necessary to respond to the many issues alluded to in the memo. The problem I have with this memo is twofold: there are several statements that are simply incorrect, and some of the deductive reasoning is questionable. I will apologize beforehand for my bluntness in this memo; however, I find it necessary due to the amount of misconceptions in areas such as: UTC, quartz oscillator theory, and time transfer techniques. As a general comment I find this discussion, NTP vs DTSS, becoming a very emotional debate. In an effort to move this discussion to a more technical plane I suggest that people specifically note their references; I have attached mine at the end of this response. TRAINING I'd like to begin with a discussion of one of my major concerns with NTP: Training of clocks (and the local clock model). Looking at Dave's NTP specification, Ref 1, page 36 I read "The Fuzzball logical-clock model, which is shown in Figure 3, can be represented as an adaptive- parameter, first-order phase lock loop, which continuously adjusts the clock phase and frequency to compensate for its intrinsic jitter, wander, and drift.? And the last two sentences of this section (ppg 37- 38) read: "The effect is to provide a broad capture range exceeding four seconds per day, yet the capability to resolve oscillator drift well below a msec per day. These characterists are appropriate for typical crystal controlled oscillators with or without temperature compensation or oven control." Given these statements I conclude: 1. that the clock model attempts to remove both short term (environmental) and long term drift components (aging and initial offset); and 2. for an uncompensated crystal oscillator one can attained a stability on the order of one part in 10**8 (ie, 1 msec/day). I disagree with both conclusions and that is why I cannot accept the NTP clock model. The influences on oscillator frequency include [REF 2-6] include: TIME - short term (noise), long term aging TEMPERATURE - static freq vs temp, thermal history (hysteresis) ACCELERATION - vibration, shock, acoustic noise IONIZING RADIATION - steady state, pulse OTHER - initial offset, power supply voltage, humidity, load impedance The above list has a number of contributors that are of more interest to DOD than the computer field. Reviewing a crystal oscillator catalog [Ref 6] one sees the main contributors being: time, temperature, initial offset and power supply voltage. Now the question becomes what are the relative magnitudes of these drift contributors. Let's look at a uncompensated (ie, without temperature compensation) 5 Mhz CMOS Clock Oscillator, VECTRON part # CO-416B option 5. The numbers are: Accuracy at 25 degrees C: +/- 10ppm 0 to 50 degrees C: +/- 5ppm Aging 3 ppm/year first year 2 ppm/year thereafter Supply Voltage little impact since it's on the order of 10**-7/% change Now assuming one has no control over the environment (ie, it may be sitting in my office or tuck away in a closet) then the noise floor is on the order of +/- 5ppm (temp stability). This may seem a little extreme, but you have to realize that a protocol designer has little control over the internal temperature gradients of a computer system. Given the background noise of +/- 5ppm, one cannot measure the error associated with aging 3 ppm/year (approx 10**-9/day). The best one can expect to do is to get close to +/- 5ppm. The bottom line is that one cannot train an oscillator in an uncompensated environment because of the noise (ie, instability due to the environment). Given this, how can the NTP clock model achieve a stability of one part in 10**8 (ie, less than a msec/day) for an uncompensated oscillator? My conversations with other people in this field indicate that it is simply not possible. Now why did we pick a number like 10**4. Well assuming a lifetime of 10 years, the stability of this oscillator would be (at the end of 10 years) about 36 ppm or 3.6 part in 10**5 (5 ppm for temp, 21 ppm for aging, 10 ppm accuracy). We felt that one part in 10**4 would be true for most of the VAX crystal oscillators. It is my belief, that one may be able to account for the error associated with the intial offset (ie, actual milling and polishing of the crystal). In the case of DTSS, one may be able to improve the clock stability from one part in 10**4 to about 1 part in 10**5. I would simply measure the error of the clock over a day (approx 10**5 seconds). Assuming I knew UTC to within 100 msec, I'd have enough significant data to calculate the oscillator drift to about one part in 10**5 (10**5 seconds/100 msec = 10**6). To do this one would need a S/W clock that is not adjusted; it must be able accumulate the error over a day. Once the new tick value is determined, one could update the timer interrupt routine. Note that this correction is orthognal to DTSS operation and need not be done that frequently? the 10**5 value would be correct for at least a year since the stability after one year would be +/- 8 ppm (5 pmm for temp and 3 ppm for aging). ------------------------------------------------------------------------ Date Tue, 3 Apr 90 5:12:09 GMT From Mills@udel.edu To Michael Soha LKG1-2/A19 226-7658 cc dennis@gw.ccie.utoronto.ca, comuzzi@took.dec.com, mills@udel.edu Subject? Re? My response to Dennis Ferguson's NTP vs DTSS memo - retry This message is in response to your reply to Dennis Ferguson's recent message about the NTP local-clock model and its implications. I would like to thank you and others at DEC for the time and care you have put into the recent message exchanges. I think we have all learned useful things that might be applied to ongoing and future projects. However, I want to make clear that my interest in pursuing this discussion is not to establish which of DTS or NTP is "better," but what can be learned to improve them or a future enhanced protocol. I realize the importance to DEC's agenda of capturing the standards process and have no personal interest in competing with this or obstructing it. Based on experience, however, I do want very much to promote that, whatever standard is adopted inside or outside the Internet community, the performance objectives attributed to NTP are at least potentially attainable, either in the emerging protocol stack or enhancements of it. I suspect Dennis might want to produce his own reply; however, I will respond to the technical points you raise. I am not including the text of either yours or Dennis' original message, since that might increase the bulk to unbearable levels. What Dennis has called "clock training" and I have called "frequency compensation" was introduced several years ago in the local-clock model adopted in NTP. The primary reason for doing this is to eliminate the need to precalibrate the inherent frequency offset of the reference oscillator and to serve as a digital filter to reduce the timing errors. In fact, the model was introduced prior to NTP and has evolved over several generations of time-transfer systems since 1979. As you know, it is described as an adaptive-parameter, first-order, type-II phase-locked loop (PLL), which is analyzed in many books, including those cited by each of us. While a type-I PLL is unconditionally stable, this type of loop cannot remove all timing errors, since it cannot compensate for frequency errors. A type-II PLL can do this, but this type of loop can become unstable, unless it is engineered according to established principles. The NTP PLL has been rigorously analyzed, designed, simulated and implemented according to these principles. The cost for this is additional architectural constants and tighter tolerances to maintain overall stability. The constants called out in the NTP spec were arrived at after substantial analysis, simulation and experiment using Internet paths ranging from high-speed LANs to those spanning the globe. A detailed mathematical analysis can be found in Appendix F of the February 1990 revision of the NTP spec, which has not appeared yet as an RFC, but can be FTPed from louie.udel.edu as the PostScript file pub/ntp/ntp.ps or I can mail you a paper copy if you wish. By the way, the local-clock algorithm described in the existing spec, Section 5, has minor errors in a couple of places, including some of the recurrence equations. This section was completely rewritten in the revised spec and several new appendices added. I am currently working on another appendix on error analysis. An important principle in the design of the local-clock algorithms was that the protocol itself should not limit the possible application to precision time and frequency transfer and that it be scalable to very high speeds, hopefully beyond a gigabit. Surely, there are no hosts today that can achieve anything remotely close to 232 picoseconds, but there are a number of time-transfer applications using special equipment where NTP might be useful, including our own gigabit network research program. The same principles arise when synchronizing mundane computers on the Internet. Not all hosts can or even need to achieve millisecond time transfer and sub-ppm stability; however, I did not want the spec or algorithms to be the limiting factors. I have explored in depth the design and capabilities of the local-clock reference oscillators found in typical computing equipment and concluded the time and frequency transfer claims made in NTP are justified. Further discussion on this point can be found in my paper in the January 1990 issue of ACM Computer Communication Review and in my paper to appear in IEEE Trans. Communications. PostScript versions of these papers can be FTPed from louie.udel.edu as the PostScript files pub/ntp/ccr.ps and pub/ntp/trans.ps or I can mail you paper copies if you wish. You call out specifications of a typical uncompensated quartz oscillator as: Accuracy at 25 degrees C: +/- 10ppm 0 to 50 degrees C: +/- 5ppm Aging 3 ppm/year first year 2 ppm/year thereafter Supply Voltage little impact since it's on the order of 10**-7/% change These specifications are in fact much better than those I find in typical computing equipment, where frequency inaccuracies up to 100 ppm, temperature sensitivities up to 1 ppm per deg C and aging rates up to 0.1 ppm per day (36 ppm per year) have been measured. By contrast, the $700 Isotemp 5-MHz OCX0s used here have a specified stability of +- 5x10^-9 from 5 to 55 deg C and aging rate of 1x10^-9 per day after 30 days. We keep them honest with a cesium oscillator calibrated by USNO. In spite of widespread mediocrity and while only a few NTP servers are equipped with precision oscillators (two have cesium oscillators (three have OCXOs and one a TCXO), the vast majority of NTP-controlled oscillators can hold frequency surprisingly well. In these oscillators the dominant error term is neither noise nor short-term stability, but temperature sensitivity. Under typical indoor conditions both in and out of machine rooms, I have often opened the PLL loop at a primary server and found it within a few milliseconds of reference time after coasting for some days without outside correction. Of course, not all oscillators conform to these anecdotal observations; however, a goal in the NTP design was to provide the highest possible performance with whatever oscillator is available. In fact, one reason for the adaptive-parameter design was to automatically optimize the loop bandwidth for the particular oscillator stability characteristics, with the baseline assumed on the basis of expected diurnal variations of a few ppm over the 24-hour period. You quite the spec: The effect is to provide a broad capture range exceeding four seconds per day, yet the capability to resolve oscillator drift well below a millisecond per day. These characteristics are appropriate for typical crystal controlled oscillators with or without temperature compensation or oven control. The intent is to state that the characteristics are appropriate for oscillators with and without temperature compensation (indeed, the loop adapts to each type) and (with the appropriate oscillator) stabilities of a millisecond per day are achievable. I hope the quote was not misleading. For clarification on a few other points you raise, note that the NTP PLL does not attempt to compensate for quartz aging, which results in a gradual change in frequency over time. This of course requires a type- III PLL, which is in fact used in some disciplined secondary frequency standards built for digital telephone network synchronization; however, I did not feel in this case that the additional complexity required would be justified. I did in fact experiment with a second-order type-II PLL in order to further minimize the phase noise, but this raised problems due to the tight constraints on update intervals. The type-II loop is stable throughout the range that results in two-way reachability. Your note suggests an alternative to the perceived complexity of the NTP PLL is a manual observation of the frequency error measured over a day, which could presumably be done at installation and saved in a file for recall at system reboot. This is exactly what Dennis has done. It might be just as easy to equip the oscillator module with a trimmer capacitor and trim out the error when the module is built. However, the intent in NTP was to do this automatically, with the startup value used only if available and in order to reduce the initial convergence time. Following are specific responses to some of your technical comments. Dennis may have some more of his own. Your quote from "Modern Control Engineering" by Ogata, p. 7: From the point of view of stability, the open loop control system is easier to build since stability is not a major problem. On the other hand, stability is always a major problem in the closed loop system since it may tend to overcorrect errors which cause oscillations of constant or changing amplitude". You go on to say a type-II system is more apt to be unstable than a type-I. Since both DTS and NTP derive timestamps relative to the local clock, both are certainly closed-loop systems. As mentioned previously, type-I systems (DTS) are unconditionally stable; however, type-II systems can be stabilized through good engineering design such as alleged in NTP. I can't answer the question of whether this is the best design appropriate for all conditions; however, the design has been validated over the sometimes ludicrously large envelope of conditions found in Internet LANs and WANs over the past decade. Your comment on "UTC accuracy to the nanosecond" requires frequent trips to USNO, of course. The proper statement should be "time transfer to the subnanosecond, UTC transfer to the limits of the available timekeeping components and time provider." GPS can achieve precisions of a few nanoseconds only if the ephemeris dither is turned off, which after the recent announcement is not likely. Kinemetrics claims their GPS time provider (with GPS receiver actually manufactured by Rockwell Collins) is accurate to 100 ns relative to USNO and 250 ns relative to UTC. As to the CCIR expectation of UTC dissemination to the microsecond, the whims of the US Congress were not respected. Current legislation requires LORAN dissemination to 500 ns and the Coast Guard expects to improve that to the order of 50 ns. Judging from measurements made by my grad student and published USNO corrections, there does not seem any chance to achieve that. On the other hand, NTP was also intended for local time transfer, for which the 232-ps resolution would seem to be justifiable. Your comments on NTP's lack of formal proofs are well taken. While these goals may have been neglected with respect to goals of performance, I think we all agree that minor changes can easily be made to NTP with the effect that claims similar to those made for DTS can be made for NTP. In fact, as experiment I crafted Marzullo's algorithm into the NTP simulator I use for evaluation and am testing it as part of the algorithmic components. The result is no decrease in accuracy and, presumably, a correctness capability. Note that the NTP "inaccuracy" is calculated in the same way as DTS, but includes only a maximum bound on the frequency error per day. You make an important point about estimating the state of the network at one time based on observations about its state at another. I worry about this, too, and have accumulated a rather large collection of measurement data between NTP servers in the Internet. Some conclusions on this issue can be found in the papers cited above. In particular, I have used NTP on many occasions as a management tool to detect changes in network routing and as an alert for congestion conditions. The fact that it runs continuously and produces accuracies to the order of a few milliseconds on most primary and secondary servers relative to extant path delays has proved a highly useful diagnostic tool. Your comment that one-way delay asymmetries can lead to estimation errors applies to both DTS and NTP, of course. However, most NTP servers run the protocol with at least three peers via diverse paths and some of them use the algorithms described in the 1978 NBS monograph you reference to reduce the errors. The February 1990 spec revision describes how this is done and presents the statistical justification for it. In practice, asymmetries as large as the 100 ms you report are quite rare on the Internet, although those of 10-20 ms are common and some (US-European) paths are as high as 70 ms. Mixed satellite- terrestrial paths have in the past haunted us, but the only ghost left now seems the USAN network. While I realize our recent message exchanges have required substantial time investments for each of us, I would like to again emphasize the value of an ongoing dialog within the research and engineering communities. I have strived to maintain an objective and productive tone in these exchanges and would like to encourage you to share ideas, experiences and even flames with us and to participate in experiment opportunities as they develop. ------------------------------------------------------------------------ Date: Tue, 3 Apr 90 19:42:38 EST From: Dennis Ferguson To: soha@nerva.enet.dec.com Cc: comuzzi@took.dec.com, mills@udel.edu Subject: Re? My response to Dennis Ferguson's NTP vs DTSS memo - retry I must apologize for the tone of the last message. Chalk it up to a little bit of frustration concerning the course things seemed to be taking. Let me make it very clear that my interests are in good quality network timekeeping. I have some understanding of the issues, and I like implementing software which does this stuff well. I have no emotional attachment to either NTP's, or anyone else's, packet or timestamp formats, nor do I stand to gain much benefit from playing with this stuff. I will likely do a DTS implementation no matter what form it ends up being standardized in, I'm just not going to like it much if it isn't a good protocol. What I do like is good quality timekeeping. I suspect NTP's encounter with DTS will make it a better, more usable protocol, At this point you can bet that NTP version 3 will include a correctly determined uncertainty interval, and very likely won't go out without an autoconfiguration protocol and procedures for authentication key management as well as an SNMP MIB. None of these conflict with the machinery that NTP already includes, which is very good at keeping your clock accurate. What bothers me is that I would not like to see an international standard timekeeping protocol which is substantially less accurate than NTP, just because at this stage there is just no reason for it. The idea of not providing frequency compensation for your system clock is hence a wee bit shocking, and I also see no reason for you to ignore the NTP clock selection/combination procedures as long the offset it produces lies within the uncertainty interval. Incorporating the authentication procedures within the protocol, while unclean, also has its advantages. In any event, I won't go on for long here since Dave has covered most of the issues and I'd rather spend the time implementing whatever he produces in the way of "correct NTP", if only to prove that one can be both correct and accurate with one's timekeeping. Just a couple of additions to Dave's comments on frequency compensation (I didn't call it clock training, either) of the local clock. The code implements a PLL, this is certainly covered in Time and Frequency Fundamentals and is common place in the time keeping industry. Indeed, if you pry the cover off of a good quality IRIG-? time code receiver (I have technical documentation for several made by Trak Systems), or even a good quality WWVB or GOES receiver, you will very likely find a microprocessor inside which implements pretty much the same procedure to synchronize the local oscillator (this is often called a "disciplined oscillator" in the advertising brochures). Further, NTP's local clock really is separate and distinct from the network time exchange protocol (whether NTP or DTS). It is actually part of the kernel in fuzzballs, and Dave has been encouraging Louie Mamakos to insert it into the 4.4 BSD kernel behind the adjtime() interface (something which I have some reservations about, but certainly not on the basis of it being NTP-specific. It just isn't). NTP's local clock is not a timekeeping protocol, it sits behind the timekeeping protocol and receives offset estimates from the latter. Your comment about "DTS and NTP are both timekeeping protocols" was way off the mark. You are right that there are tradeoffs between the type II control loop that NTP uses and DTS' type I control. Note that an error in frequency in essence presents a ramp input, whose slope is the frequency error (or drift), to your control loop. The slope of the input sometimes changes (usually with temperature, I have a plot pegged to the wall beside my desk of the temperature calibration of the crystal in my workstation, measured with NTP. The slope is about -1.1 ppm/C), though changes to the frequency error are normally quite small compared to the longer-term average. The NTP type II loop does several things right. First, it tracks the ramp input (i.e. the frequency error) with zero steady state error. It will also track changes in the frequency error (i.e. "drift" variations) fairly accurately if they occur slowly enough. DTS can't do this, it exhibits a steady state error when tracking a ramp proportional to the slope. Changes in the slope change the steady state error. Second, because the time constant of the loop is fairly long, the NTP type II loop tends to damp out statistical noise in the data you are trying to phase lock to (i.e. the offsets produced by the time exchange protocol). DTS' type I loop, however, allows this jitter right through to the system clock. Third, while unrelated to type I versus type II, the NTP local clock applies an adjustment to the system clock by making little tiny adjustments once every 4 seconds, rather than all at once. This spreading out of the adjustment avoids the high frequency jitter that is otherwise caused. Note that for the archtypical, 100 ppm frequency error, DTS synchronized clock, we've agreed that the system clock will be zooming around by 90 ms over the 15 minute update interval, with an average (steady state) error of 45 ms. The NTP local clock, when faced with a 100 ppm error for which it doesn't know the correction, (this can happen when you run the daemon on a machine for the first time, it is analogous to a large step change in the slope of the signal you are tracking) will exhibit a transient error which is initially about 40 ms in magnitude as well, but this will be stable without the big jitter. What you lose for this is speed in correcting step changes in the clock condition. DTS can correct the system clock offset which can occur at startup in the first update. Similarly, DTS will almost immediately assume the steady state operating condition as soon as it is started on a machine. Offsets due to lost clock interrupts are corrected within an update or two as well. The NTP local clock takes longer to correct these types of events, and/or requires a higher update rate while doing so. Now the tradeoff. Local oscillators whose frequency is wrong, and whose frequency varies, are a fact of life. This is very nearly always the case. Likewise, statistical jitter in the offsets produced by the timekeeping protocol (whether NTP or DTS) is equally unavoidable, so damping of these fluctuations is highly desireable. Thus the NTP local clock deals with the common case (a system clock whose frequency is inaccurate and which varies somewhat, and somewhat noisy data from the network) much more accurately than DTS' type I control. On the other hand, it corrects startup transients and responds to step changes due to things like lost clock interrupts, more slowly than DTS does (it deals with these things, but at a more stately pace). Note that the latter are exceptions, however, since you start the protocol infrequently and you hope you don't lose clock interrupts at all. Thus the NTP local clock optimizes performance in the ordinary case at some expense to speed when handling exceptional conditions. I think this is a good engineering tradeoff. I think frequency compensation of the system clock is a must for DTS, and I'm not going to be happy if it progresses towards standardhood without it. I'm also not convinced that you shouldn't be looking at the way NTP filters and selects samples, since this does measureably improve your time but certainly doesn't preclude the calculation of a correct uncertainty interval. I think I may have said enough, since I obviously have yet to convince anyone. The more I consider it, though, the more I think the correctness-and-management versus performance tradeoff is just so much baloney. These issues are all separable, I see no reason why you can't have everything in one protocol. I think rather than trying to argue this position, however, it might be better to spend the time on producing a correct, autoconfiguring, accurate NTP that I can give to people so that no one at the standards committee will believe you if you try to foist this argument off on them. By the way, it occurs to me that an NTP which computes a correct uncertainty interval will allow us to make head-to-head performance comparisons between DTS and NTP. If both protocols compute provably correct inaccuracies, but one consistantly produces a smaller inaccuracy on the same machines via the same network paths, is not the latter a better, more useful protocol? I think so, and I have a distinct feeling both NTP's local clock and clock filters are going to make this quite interesting. We may be able to convince you DTS needs some of this stuff after all. ------------------------------------------------------------------------