Clock synchronization

Last updated

Clock synchronization is a topic in computer science and engineering that aims to coordinate otherwise independent clocks. Even when initially set accurately, real clocks will differ after some amount of time due to clock drift, caused by clocks counting time at slightly different rates. There are several problems that occur as a result of clock rate differences and several solutions, some being more acceptable than others in certain contexts. [1]

Contents

Terminology

In serial communication, clock synchronization can refer to clock recovery which achieves frequency synchronization, as opposed to full phase synchronization. Such clock synchronization is used in synchronization in telecommunications and automatic baud rate detection. [2]

Plesiochronous or isochronous operation refers to a system with frequency synchronization and loose constraints on phase synchronization. Synchronous operation implies a tighter synchronization based on time perhaps in addition to frequency.

Problems

As a result of the difficulties managing time at smaller scales, there are problems associated with clock skew that take on more complexity in distributed computing in which several computers will need to realize the same global time. For instance, in Unix systems the make command is used to compile new or modified code and seeks to avoid recompiling unchanged code. The make command uses the clock of the machine it runs on to determine which source files need to be recompiled. If the sources reside on a separate file server and the two machines have unsynchronized clocks, the make program might not produce the correct results. [3]

Synchronization is required for accurate reproduction of streaming media. Clock synchronization is a significant component of audio over Ethernet systems.

Solutions

In a system with a central server, the synchronization solution is trivial; the server will dictate the system time. Cristian's algorithm and the Berkeley algorithm are potential solutions to the clock synchronization problem in this environment.

In distributed computing, the problem takes on more complexity because a global time is not easily known. The most used clock synchronization solution on the Internet is the Network Time Protocol (NTP) which is a layered client-server architecture based on User Datagram Protocol (UDP) message passing. Lamport timestamps and vector clocks are concepts of the logical clock in distributed computing.

In a wireless network, the problem becomes even more challenging due to the possibility of collision of the synchronization packets on the wireless medium and the higher drift rate of clocks on low-cost wireless devices. [4] [5]

Berkeley algorithm

The Berkeley algorithm is suitable for systems where a radio clock is not present. This system has no way of making sure of the actual time other than by maintaining a global average time as the global time. A time server will periodically fetch the time from all the time clients, average the results, and then report back to the clients the adjustment that needs be made to their local clocks to achieve the average. This algorithm highlights the fact that internal clocks may vary not only in the time they contain but also in the clock rate.

Clock-sampling mutual network synchronization

Clock-sampling mutual network synchronization (CS-MNS) is suitable for distributed and mobile applications. It has been shown to be scalable over mesh networks that include indirectly-linked non-adjacent nodes, and is compatible with IEEE 802.11 and similar standards. It can be accurate to the order of few microseconds, but requires direct physical wireless connectivity with negligible link delay (less than 1 microsecond) on links between adjacent nodes, limiting the distance between neighboring nodes to a few hundred meters. [6]

Cristian's algorithm

Cristian's algorithm relies on the existence of a time server. [7] The time server maintains its clock by using a radio clock or other accurate time source, then all other computers in the system stay synchronized with it. A time client will maintain its clock by making a procedure call to the time server. Variations of this algorithm make more precise time calculations by factoring in network radio propagation time.

Satellite navigation systems

In addition to its use in navigation, the Global Positioning System (GPS) can also be used for clock synchronization. The accuracy of GPS time signals is ±10 nanoseconds. [8] Using GPS (or other satellite navigation systems) for synchronization requires a receiver connected to an antenna with unobstructed view of the sky.

Inter-range Instrumentation Group time codes

IRIG timecodes are standard formats for transferring timing information. Atomic frequency standards and GPS receivers designed for precision timing are often equipped with an IRIG output. The standards were created by the Telecommunications Working Group of the United States military's Inter-Range Instrumentation Group (IRIG), the standards body of the Range Commanders Council. Work on these standards started in October 1956, and the original standards were accepted in 1960. [9]

Network Time Protocol

Network Time Protocol (NTP) is a highly robust protocol, widely deployed throughout the Internet. Well tested over the years, it is generally regarded as the state of the art in distributed time synchronization protocols for unreliable networks. It can reduce synchronization offsets to times of the order of a few milliseconds over the public Internet, and to sub-millisecond levels over local area networks.

A simplified version of the NTP protocol, Simple Network Time Protocol (SNTP), can also be used as a pure single-shot stateless primary/secondary synchronization protocol, but lacks the sophisticated features of NTP, and thus has much lower performance and reliability levels.

Precision Time Protocol

Precision Time Protocol (PTP) is a master/slave protocol for delivery of highly accurate time over local area networks.

Reference broadcast synchronization

The Reference Broadcast Time Synchronization (RBS) algorithm is often used in wireless networks and sensor networks. In this scheme, an initiator broadcasts a reference message to urge the receivers to adjust their clocks.

Reference Broadcast Infrastructure Synchronization

The Reference Broadcast Infrastructure Synchronization (RBIS) [10] protocol is a master/slave synchronization protocol, like RBS, based on a receiver/receiver synchronization paradigm. It is specifically tailored to be used in IEEE 802.11 wireless networks configured in infrastructure mode (i.e., coordinated by an access point). The protocol does not require any modification to the access point.

Synchronous Ethernet

Synchronous Ethernet uses Ethernet in a synchronous manner such that when combined with synchronization protocols such as PTP in the case of the White Rabbit Project, sub-nanosecond synchronization accuracy is achieved.

Wireless ad hoc networks

Synchronization is achieved in wireless ad hoc networks through sending synchronization messages in a multi-hop manner and each node progressively synchronizing with the node that is the immediate sender of a synchronization message. Examples include Flooding Time Synchronization Protocol (FTSP), [4] and Harmonia, [5] both able to achieve synchronization with accuracy on the order of microseconds.

Huygens

Researchers from Stanford and Google introduced Huygens, a probe-based, end-to-end clock synchronization algorithm. Huygens is implemented in software and thus can be deployed in data centers or in public cloud environments. By leveraging some key aspects of modern data centers, and applying novel estimation algorithms and signal processing techniques, the Huygens algorithm achieved an accuracy of tens of nanoseconds even at high network load. [11] The findings of this research are being tested in financial market applications. [12]

See also

Related Research Articles

<span class="mw-page-title-main">Leap second</span> Extra second inserted to keep civil time in sync with the Earths rotation

A leap second is a one-second adjustment that is occasionally applied to Coordinated Universal Time (UTC), to accommodate the difference between precise time and imprecise observed solar time (UT1), which varies due to irregularities and long-term slowdown in the Earth's rotation. The UTC time standard, widely used for international timekeeping and as the reference for civil time in most countries, uses TAI and consequently would run ahead of observed solar time unless it is reset to UT1 as needed. The leap second facility exists to provide this adjustment. The leap second was introduced in 1972. Since then, 27 leap seconds have been added to UTC, with the most recent occurring on December 31, 2016. All have so far been positive leap seconds, adding a second to a UTC day; while it is possible for a negative leap second to be needed, one has not happened yet.

Time and frequency transfer is a scheme where multiple sites share a precise reference time or frequency. The technique is commonly used for creating and distributing standard time scales such as International Atomic Time (TAI). Time transfer solves problems such as astronomical observatories correlating observed flashes or other phenomena with each other, as well as cell phone towers coordinating handoffs as a phone moves from one cell to another.

The data link layer, or layer 2, is the second layer of the seven-layer OSI model of computer networking. This layer is the protocol layer that transfers data between nodes on a network segment across the physical layer. The data link layer provides the functional and procedural means to transfer data between network entities and may also provide the means to detect and possibly correct errors that can occur in the physical layer.

<span class="mw-page-title-main">Network Time Protocol</span> Standard protocol for synchronizing time across devices

The Network Time Protocol (NTP) is a networking protocol for clock synchronization between computer systems over packet-switched, variable-latency data networks. In operation since before 1985, NTP is one of the oldest Internet protocols in current use. NTP was designed by David L. Mills of the University of Delaware.

<span class="mw-page-title-main">Radio clock</span> Type of clock which self-synchronizes its time using dedicated radio transmitters

A radio clock or radio-controlled clock (RCC), and often colloquially referred to as an "atomic clock", is a type of quartz clock or watch that is automatically synchronized to a time code transmitted by a radio transmitter connected to a time standard such as an atomic clock. Such a clock may be synchronized to the time sent by a single transmitter, such as many national or regional time transmitters, or may use the multiple transmitters used by satellite navigation systems such as Global Positioning System. Such systems may be used to automatically set clocks or for any purpose where accurate time is needed. Radio clocks may include any feature available for a clock, such as alarm function, display of ambient temperature and humidity, broadcast radio reception, etc.

<span class="mw-page-title-main">DCF77</span> German time signal radio station

DCF77 is a German longwave time signal and standard-frequency radio station. It started service as a standard-frequency station on 1 January 1959. In June 1973 date and time information was added. Its primary and backup transmitter are located at 50°0′56″N9°00′39″E in Mainflingen, about 25 km south-east of Frankfurt am Main, Germany. The transmitter generates a nominal power of 50 kW, of which about 30 to 35 kW can be radiated via a T-antenna.

<span class="mw-page-title-main">Time server</span> A server that reads actual time information and distributes it

A time server is a server computer that reads the actual time from a reference clock and distributes this information to its clients using a computer network. The time server may be a local network time server or an internet time server.

<span class="mw-page-title-main">Clock network</span> Set of clocks that are automatically synchronized to show the same time

A clock network or clock system is a set of synchronized clocks designed to always show exactly the same time by communicating with each other. Clock networks usually consist of a central master clock kept in sync with an official time source, and one or more slave clocks which receive and display the time from the master.

<span class="mw-page-title-main">OpenNTPD</span> Implementation of the Network Time Protocol

OpenNTPD is a Unix daemon implementing the Network Time Protocol to synchronize the local clock of a computer system with remote NTP servers. It is also able to act as an NTP server to NTP-compatible clients.

The Precision Time Protocol (PTP) is a protocol for clock synchronization throughout a computer network with relatively high precision and therefore potentially high accuracy. In a local area network (LAN), accuracy can be sub-microsecond – making it suitable for measurement and control systems. PTP is used to synchronize financial transactions, mobile phone tower transmissions, sub-sea acoustic arrays, and networks that require precise timing but lack access to satellite navigation signals.

A pulse per second is an electrical signal that has a width of less than one second and a sharply rising or abruptly falling edge that accurately repeats once per second. PPS signals are output by radio beacons, frequency standards, other types of precision oscillators and some GPS receivers. Precision clocks are sometimes manufactured by interfacing a PPS signal generator to processing equipment that aligns the PPS signal to the UTC second and converts it to a useful display. Atomic clocks usually have an external PPS output, although internally they may operate at 9,192,631,770 Hz. PPS signals have an accuracy ranging from 12 picoseconds to a few microseconds per second, or 2.0 nanoseconds to a few milliseconds per day based on the resolution and accuracy of the device generating the signal.

<span class="mw-page-title-main">Phasor measurement unit</span> Device measuring electrical waves on a power grid

A phasor measurement unit (PMU) is a device used to estimate the magnitude and phase angle of an electrical phasor quantity in the electricity grid using a common time source for synchronization. Time synchronization is usually provided by GPS or IEEE 1588 Precision Time Protocol, which allows synchronized real-time measurements of multiple remote points on the grid. PMUs are capable of capturing samples from a waveform in quick succession and reconstructing the phasor quantity, made up of an angle measurement and a magnitude measurement. The resulting measurement is known as a synchrophasor. These time synchronized measurements are important because if the grid’s supply and demand are not perfectly matched, frequency imbalances can cause stress on the grid, which is a potential cause for power outages.

Cristian's algorithm is a method for clock synchronization which can be used in many fields of distributive computer science but is primarily used in low-latency intranets. Cristian observed that this simple algorithm is probabilistic, in that it only achieves synchronization if the round-trip time (RTT) of the request is short compared to required accuracy. It also suffers in implementations using a single server, making it unsuitable for many distributive applications where redundancy may be crucial.

Reference Broadcast Synchronization (RBS) is a synchronization method in which the receiver uses the physical layer broadcasts for comparing the clocks. This slightly differs from traditional methods which synchronize the sender's with the receiver's clock.

Synchronous Ethernet, also referred as SyncE, is an ITU-T standard for computer networking that facilitates the transference of clock signals over the Ethernet physical layer. This signal can then be made traceable to an external clock.

High-availability Seamless Redundancy (HSR) is a network protocol for Ethernet that provides seamless failover against failure of any single network component. PRP and HSR are independent of the application-protocol and can be used by most Industrial Ethernet protocols in the IEC 61784 suite. HSR does not cover the failure of end nodes, but redundant nodes can be connected via HSR.

Two independent clocks, once synchronized, will walk away from one another without limit. To have them display the same time it would be necessary to re-synchronize them at regular intervals. The period between synchronizations is referred to as holdover and performance under holdover relies on the quality of the reference oscillator, the PLL design, and the correction mechanisms employed.

White Rabbit is the name of a collaborative project including CERN, GSI Helmholtz Centre for Heavy Ion Research and other partners from universities and industry to develop a fully deterministic Ethernet-based network for general purpose data transfer and sub-nanosecond accuracy time transfer. Its initial use was as a timing distribution network for control and data acquisition timing of the accelerator sites at CERN as well as in GSI's Facility for Antiproton and Ion Research (FAIR) project. The hardware designs as well as the source code are publicly available. The name of the project is a reference to the White Rabbit appearing in Lewis Carroll's novel Alice's Adventures in Wonderland.

Deterministic Networking (DetNet) is an effort by the IETF DetNet Working Group to study implementation of deterministic data paths for real-time applications with extremely low data loss rates, packet delay variation (jitter), and bounded latency, such as audio and video streaming, industrial automation, and vehicle control.

References

  1. Tanenbaum, Andrew S.; van Steen, Maarten (2002), Distributed Systems : Principles and Paradigms, Prentice Hall, ISBN   0-13-088893-1
  2. Norman Matloff (September 3, 2001), Transmission on a Serial Line (PDF), retrieved 2018-04-17
  3. Marco Platania (2018-06-03). "Clock Synchronization" (PDF). p. 11.
  4. 1 2 Maróti, Miklós; Kusy, Branislav; Simon, Gyula; Lédeczi, Ákos (2004). "The flooding time synchronization protocol". Proceedings of the 2nd international conference on Embedded networked sensor systems. SenSys '04. New York, NY, USA: ACM. pp. 39–49. doi:10.1145/1031495.1031501. ISBN   1581138792. S2CID   9897231.
  5. 1 2 Koo, Jinkyu; Panta, Rajesh K.; Bagchi, Saurabh; Montestruque, Luis (2009). "A tale of two synchronizing clocks". Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. SenSys '09. New York, NY, USA: ACM. pp. 239–252. doi:10.1145/1644038.1644062. ISBN   9781605585192. S2CID   8242938.
  6. Rentel, Carlos H.; Kunz, Thomas (March 2005), "A clock-sampling mutual network synchronization algorithm for wireless ad hoc networks", IEEE Wireless Communications and Networking Conference, 1, IEEE Press: 638–644, doi:10.1109/WCNC.2005.1424575, S2CID   1340072
  7. Cristian, F. (1989), "Probabilistic clock synchronization", Distributed Computing, 3 (3), Springer: 146–158, doi:10.1007/BF01784024, S2CID   3170166
  8. "Common View GPS Time Transfer". National Institute of Standards and Technology. Archived from the original on 2012-10-28.
  9. Josh Matson (May 2013). "Choosing the correct Time Synchronization Protocol and incorporating the 1756-TIME module into your Application" (PDF). Rockwell Automation. Retrieved 2019-08-13.
  10. Cena, G.; Scanzio, S.; Valenzano, A.; Zunino, C. (June 2015), "Implementation and Evaluation of the Reference Broadcast Infrastructure Synchronization Protocol", IEEE Transactions on Industrial Informatics, 11 (3), IEEE Press: 801–811, doi:10.1109/TII.2015.2396003, S2CID   17867070
  11. Exploiting a Natural Network Effect for Scalable, Fine-grained Clock Synchronization. 2018. pp. 81–94. ISBN   9781939133014.
  12. John Markoff (June 29, 2018). "Time Split to the Nanosecond Is Precisely What Wall Street Wants". New York Times.

Further reading