Internet Timekeeping Around the Globe
D.L. Mills, A. Thyagarajan and B.C. HuffmanElectrical and Computer Engineering DepartmentUniversity of Delaware
Abstract
This paper describes a massive survey of Network Time Protocol (NTP) servers and clients in order to discover statistics of time and frequency errors, as well as determine the health and welfare of the NTP synchronization subnet operating in the global Internet. Among the conclusions of the survey are that most NTP clients are within 10 ms of their servers and all are within 20 ms on average. However, additional errors up to one-half the roundtrip delay are possible, but relatively rare. There is, however, a disturbing incidence of improperly operating servers and misguided server configurations.
Keywords: computer time, network time, time synchronization
introduction
Timekeeping via the Internet has become a ubiquitous service extending to well over 100,000 public servers and clients in many countries of the world. In addition, an uncounted number of private servers and clients lurk behind the firewalls of many large government and corporate networks. There have been several previous studies [] which have compiled population and accuracy statistics using time-dissemination protocols such as the Network Time Protocol (NTP) and others. However, only [] considered reaching out to all hosts and routers in the global Internet. That study indexed the Domain Name System database of eight years ago and found about 21,000 hosts that returned time in one fashion or another. The newer studies used only a small population to evaluate protocol and algorithm improvements over the years since then.
Since the present day Internet has experienced an explosion of numbers, it is no longer acceptable or even possible to survey Internet hosts and routers by indexing a public directory service. However, it is possible to discover them for an organized subnetwork such as used by NTP. This paper presents a comprehensive survey of the NTP servers operating in the global Internet of today. While the search engine used in the survey could find only a fraction of all NTP outposts on the public Internet, it did find some 182,000 network paths used by 36,000 servers, 230 of these synchronized to UTC via radio, satellite or modem. Uncounted others, including large numbers of personal workstations operating as broadcast clients, escaped detection. The survey measured the time offsets of each client relative to its server, as well as related variables important to the health and welfare of the NTP subnet itself.
A comprehensive description of the NTP architecture, protocol and algorithms is beyond the scope of this paper, but can be found in [] and citations found there. Briefly, the NTP timekeeping network consists of a hierarchical tree of primary (stratum 1) time servers at the root. These provide synchronization to secondary servers at increasing stratum levels (hops) to the leaves of the tree. A server sends a message to one or more other peer servers and expects replies from each of them at some later time. From the four timestamps obtained upon departure and arrival of the request and response messages, the server calculates the clock offset and roundtrip delay relative to its peer. A suite of crafted algorithms selects the best measurements from each server and the best combination of several servers operating independently. The actual clock time and frequency are disciplined using an adaptive parameter, hybrid phase/frequency-lock loop.
The Survey
The survey which generated the bulk of the results presented in this paper was performed over some months in late 1995. The goal was to find as many NTP servers operating in the Internet as practical and determine their performance with respect to time and frequency errors, as well as the robustness and stability of the NTP subnet itself. The results serve as a baseline calibration of the subnet performance, as well useful insights into subnet configuration and security management strategies.
The search engine used a variety of techniques, ranging from indexing available public databases to exploring the Internet NTP subnet in real time with available monitoring protocols and tools. In the following, the term subnet without the qualifier NTP means any subtree of the global NTP subnet tree. The strategy was to identify as many servers as possible from public lists, such as the database of public servers maintained at the NTP web page. There are currently 69 public primary (stratum 1) servers and 105 public secondary (stratum 2) listed in that database. These servers were queried using NTP monitoring and control protocols to identify their client servers. In the next round, those servers were queried to identify their client servers. The survey continued for many rounds until no new servers could be found. Occasionally, the identity of a new server was discovered by other means and the survey continued for new rounds as necessary.
It was vital in the planning and execution of the survey to avoid network and server congestion due to the query messages themselves. Therefore, the intervals between messages were randomized over moderately long intervals in the order of minutes. Due to the volume of data involved, individual rounds required up to days to complete and the entire survey required many rounds. 
The data for each server consists of a spreadsheet, where each line of the spreadsheet corresponds to a protocol instantiation, called an association, between the server and its source of synchronization, or peer, either another server or a primary reference clock, usually a GPS receiver. Typical server configurations include several associations, which run simultaneously in order to provide redundancy and diversity. The association data includes the endpoint Internet addresses, stratum, mode, reachability status, relative clock offset, roundtrip delay and error estimate.
Each association operates in a designated mode, depending on whether the server can synchronize the peer or whether the peer can synchronize the server. Symmetric modes are used when either peer can synchronize the other and is often used for mutual backup in multiple-peer subnets. Client/server modes are used in subnets of modest size and where the highest accuracy is required. Broadcast modes are used in large subnets where the delays are small and the accuracy requirements not demanding.
The data analysis phase of the project considered 230,774 associations, but discarded 818 with misconfigured servers, 141 with multicast servers, 3,532 with broadcast servers, 25,640 with unreachable servers, 17,195 with invalid stratum and 1,293 duplicates, leaving 180,520 representing valid measurements of clock offset and roundtrip delay. In these, 36,478 distinct Internet addresses were found, each identifying a NTP server. It should be noted that these servers represent only a fraction of all servers in the NTP subnet. Clients operating in broadcast mode were not found, as well as many others on private networks or behind firewalls. Since these statistics were determined, a few additional valid associations were found, bringing the total to 182,538.
In the above totals, there were 3,673 servers operating in broadcast modes. The number of clients of these servers is unknown, since broadcast clients ordinarily do not exchange messages with their servers. In fact, most broadcast servers have tens to hundreds of clients, so the actual client population is considerably underestimated. The 1,293 duplicates represent symmetric associations, where each of two peers agree to back up the other. Ordinarily, the offsets measured by symmetric peers have nearly the same magnitude, but opposite sign, and the delays are nearly the same, but this was not a factor in the analysis.
Table x shows the number of servers and clients by stratum. Of 182,538 associations, 13,880 represent servers that provide synchronization to the remaining 16,8658 servers at the leaf nodes of the subnet tree. The maximum number of clients per server is 652, but this understates the true value, since the maximum number the server monitoring cache can hold is near this number. From other data discussed later, higher values to 734 have been observed on one server which is certainly not the most heavily loaded. The fact that at most stratum levels the maximum and the top ten have about the same number of clients and the overall average is much lower suggests the population is dominated by a relatively small number of heavily loaded servers and the remainder relatively lightly loaded. About half the number of servers operate at stratum 3, which usually function as department servers dependent on redundant campus servers operating at stratum 2. The servers shown operating at stratum 6 and above are very likely broken.
Performance Indicators
The three most significant factors that affect timekeeping accuracy are network jitter, oscillator frequency stability and asymmetric network delays. The influence of these three factors varies widely in the NTP subnet, depending on the particular network path and particular oscillator implementation. The survey results allow each of these factors to be studied, evaluated and displayed as histograms, graphs and tables, and statistics derived from them. However, the survey was conducted over a period of months, where the particular network conditions were not completely stationary. For this reason, the results should be regarded as an approximation to a true snapshot.
Time Offsets
The most important indicator of timekeeping performance is the time offset measured by the client relative to its server for each association. The survey results for 19,873 servers were analyzed to determine the time offsets. From this population, 1,084 servers were discarded as unsynchronized at the time of the survey. Figure x shows a histogram of time offsets for the remaining 18,679 servers, from which the median is 7.5 ms and mean 15.9 ms. Note that these results represent the global population at large, whereas clients on typical LANs have offsets generally less than a millisecond.
In the present NTP design, each server on the path from the client to the primary server independently disciplines its clock relative to the servers at the next lower stratum, in order to provide a stable, low-jitter reference for local applications. Thus, the figure shows the offset of a client relative to its server, not the offset relative to the primary servers at the root of the NTP subnet. In principle, the protocol could determine this by accumulating the offsets on each hop along the path to the primary servers. However, this statistic would accumulate large jitter and be unsuitable if used to discipline the system clock. In the interest of an economical packet header, it was not included in the NTP protocol design. 
Frequency Offsets
The NTP clock discipline algorithm operates to minimize both time and frequency errors. To the extent it makes good predictions based on measured time offsets produced by the protocol, time errors due to systematic frequency offsets can be minimized. However, in order to provide millisecond accuracies with measurement intervals up to 1024 s, it is necessary to estimate the current frequency to less than one PPM, even when the systematic frequency offset is hundreds of PPM. The survey results for 19,873 servers were analyzed to determine the systematic frequency offset. From this population, 989 servers were discarded as unsynchronized at the time of the survey. Figure x shows a histogram of systematic frequency offsets for the remaining 18,884 servers, from which the median is 38 PPM and mean 78 PPM.
While most clock oscillators are moderately well behaved, there is a significant tail on the distribution. The results demonstrate that the NTP clock discipline must have a very large capture range and an adaptive time constant. In the present design, the capture range is over 500 PPM and the time constant varies with the measurement interval from 64 s to 1024 s.
Asymmetric Delays
The NTP protocol design does not permit an absolute measurement of time difference between servers, unless an external common-view means is available. As a result, clock offset errors cannot be distinguished from Asymmetric network delays. There is evidence to suggest that errors due this cause are not uncommon; however, by design the errors due to asymmetric delays are bounded by half the roundtrip delay, although errors this large are rare. Figure x shows a histogram of the delays measured between the 18,884 servers used in the offset measurements. The results show maximum delay 1.9 s, median 118 ms and mean 173 ms. Figure x shows the cumulative probability distribution function for servers on the same network number (lower curve) and on different networks (upper curve). As with other survey data analyzed, the tails on the distributions can be very long. From anecdotal evidence, this is due to the widely varying incidence of congestion in the Internet of modern times.
From anecdotal evidence and previously reported results [], the delay asymmetry is seldom more than one-tenth the roundtrip delay. For LANs with delays in the low milliseconds, the error contributions are generally negligible. Even on long paths spanning the Atlantic where propagation delays dominate, the errors are small compared to those due to network jitter. However, in cases where one direction uses cable and the other satellite, for example, or where two peers are connected to different providers with very different network grids, the errors can be substantial.
Health Indicators
A good idea of the general health of the NTP subnet can be determined from the status code maintained for each association. Table x shows a breakdown of the 182,538 associations considered in the analysis. The table is best interpreted starting from the bottom. At each step upward from the bottom, the indicated number of associations are discarded for the reason given on the same line. The line under the heading line shows the number of associations actually used to discipline the system clock.
A few notes will clarify the operations involved. The intersection algorithm detects and discards associations which show a time interval outside the correct time interval determined for the majority of associations. Standby associations are those deemed correct, but not among the lowest ten in order of increasing estimated error (synchronization distance). The relatively high number of standby associations was traced to a provider using a very misguided configuration where each of about 100 NTP servers maintained associations with all of the others. The clustering algorithm repeatedly discards outlyer associations until either a minimum number of three remain or the residual sample variance cannot be reduced by further discards. The remaining population, including the top three lines in the table, represent candidate associations considered the pick of the litter. Selection among the candidates to determine the ones actually used to discipline the system clock is determined on the basis of estimated error, with the offset provided to the clock discipline computed as a weighted average of the available candidates.
Primary Servers
The accuracy and stability of the global NTP subnet depends on the reference clocks used to synchronize the primary servers. There are many different means used to do this, including radio, satellite, telephone modem and cesium clock ensemble. Table x shows the population characteristics of the 231 primary reference clocks found in the survey. Since this survey was completed, the national time services of France, Chile and Italy have been added and additional time servers operated by NIST and USNO have come online, making the total operating today significantly larger. The surprisingly large number of DCF77 reference clocks is undoubtably due to the very inexpensive receivers available for this signal in Europe. In the interval since this survey was completed, and as inexpensive GPS receivers have come on the market, new servers are using GPS. In addition to the 231 primary servers found, some 88 servers were found where the reference clock had either failed or had been misconfigured.
In some configurations, a special reference clock driver provides backup when all other sources fail. The driver simulates a reference clock operating at some higher stratum, usually 3. If all sources of lower stratum fail, the free-running server system clock becomes the NTP reference and the clients depending on the server synchronize to it. At the time of the survey, 1,502 servers were found to use this feature.
A Day in the Live of a Busy NTP Server
While some NTP servers are dedicated timekeepers, most serve other functions as well, including those of routers, file servers and ordinary workstations. It is of some concern to determine how much the resource requirements of the timekeeping function impact on these other functions. Of principle concern are the processing and network overhead resulting from client requests to a busy time server.
Timekeeper rackety.udel.edu, one of the most experienced timekeepers in the business, is a well known primary time server with clients all over the world. This Sun Microsystems SPARCstation IPC functions as a file server. print server and router as well, although in this machine these functions have low demand. An Austron 2201A GPS receiver functions as the primary reference clock and a Spectracom WWVB receiver as the backup reference clock. The operating system kernel is modified to use the pulse-per-second signal from a Hewlett Packard 5061A cesium oscillator to discipline the system clock generally within a few tens of microseconds. While implemented expressly for the SunOS operating system, the kernel modifications are also in current Digital Unix and Solaris operating systems.
In order to assess the resource requirements of the timekeeping function, ordinary Unix commands were used to measure the CPU time consumed by the NTP daemon over about a day, which came to 1.54 percent. A network sniffer program captured all of the NTP packets that flew the wire during that time and saved them for later analysis. The 734 clients sent an average of 6.4 packets per second, which corresponds to a mean interarrival interval of 157 s for each client.
Each input packet generated on average 0.64 output packets and required a total of 2.4 ms of CPU time for the request/response transaction. It is not known how many of the 734 clients were using cryptographic authentication; but, if so, the time to generate the request and response cryptosums on an IPC is about 300 us, but only about 30 us on an UltraSPARC 170.
Rackety is connected via a 10-Mb/s Ethernet, routers and 1.544 Mb/s T1 circuits to Internet backbone networks. While the T1 circuits are not dedicated to NTP traffic, the other customers are few. Averaged over the day, the 76-octet NTP packet rate was measured at 10.5 packets per second. Exclusive of overhead bits, this is .064 percent of the Ethernet capacity or 0.21 percent on each direction of the T1 capacity. The conclusion to be drawn here is that the resources required for NTP are minimal, even when hundreds of clients are involved and even with a slow processor.
Conclusions
The results of the survey demonstrate that most NTP clients are within 10 ms of their servers and all are within 20 ms on average. There may be additional errors due to asymmetrical paths, but this is bounded by one-half the roundtrip delay. While it is not possible using the NTP protocol itself to estimate the errors when multiple-hop paths are involved, a reasonable estimate may be the number of hops times these figures. It is clear from the histograms that the errors in some cases are well above these figures, in some cases due to network congestion and in other cases due to improperly operating servers or misguided choice of servers.
The roundtrip delay statistic has proven very useful, not only to assess timekeeping performance, but in the general study of the worldwide Internet performance. The fact that NTP servers determine this statistic on a regular basis suggests the use of NTP as a network monitor with a coupling to the monitoring infrastructure using the Simple Network Monitoring Protocol (SNMP). In fact, this has been done on an experimental basis and described in a report now in preparation.
Perhaps the most disturbing results of the survey is the significant fraction of servers showing improper operating parameters or incorrectly configured servers. In many cases, this is due to benign neglect of the operator, since timekeeping is not usually regarded as a revenue service and providing NTP service to the community is a volunteer sport. This problem has been addressed in the design of the next version of the NTP protocol in the form of features to discover servers and configure the NTP subnet automatically and without the chance of operator error.
references
Mills, D.L. The network computer as precision timekeeper. Proc. PTTI Meeting (December 1996).
Mills, D.L. Improved algorithms for synchronizing computer network clocks. IEEE/ACM Trans. Networks (June 1995).
Mills, D.L. Precision synchronization of computer network clocks. ACM Computer Communications Review (April, 1994).
Mills, D.L. On the accuracy and stability of clocks synchronized by the Network Time Protocol, ACM Computer Communications Review (January, 1990).