Clock synchronization: Difference between revisions

Revision as of 14:28, 14 October 2022

Latest revision as of 21:09, 25 July 2025

(14 intermediate revisions by 10 users not shown)

Line 1:

{{shortShort description|Coordination of otherwise independent clocks}}

{{broader|Clock network}}

Line 15:

==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]].<ref>{{citation |url=http://heather.cs.ucdavis.edu/~matloff/Networks/Serial/Serial.pdf |title=Transmission on a Serial Line |access-date=2018-04-17 |author=Norman Matloff |date=September 3, 2001}}</ref>

[[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 (software)|make]]'' command is used to [[compiler|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.<ref>{{cite web |url=http://www.dsn.jhu.edu/~platania/index_files/clock_sync.pdf |page=11 |title=Clock Synchronization |author=Marco Platania |date=2018-06-03}}</ref>

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

Line 27:

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 clock]]s 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 [[Network packet|packets]] on the wireless medium and the higher drift rate of clocks on low-cost wireless devices.<ref name="Miklós">{{Cite journalbook|last1=Maróti|first1=Miklós|last2=Kusy|first2=Branislav|last3=Simon|first3=Gyula|last4=Lédeczi|first4=Ákos|date=2004|title=The Flooding Time Synchronization Protocol|journal=Proceedings of the 2nd Internationalinternational Conferenceconference on Embedded Networkednetworked Sensorsensor Systemssystems |chapter=The flooding time synchronization protocol |date=2004|series=SenSys '04|___location=New York, NY, USA|publisher=ACM|pages=39–49|doi=10.1145/1031495.1031501|isbn=1581138792|s2cid=9897231}}</ref><ref name="Panta">{{Cite journalbook|last1=Koo|first1=Jinkyu|last2=Panta|first2=Rajesh K.|last3=Bagchi|first3=Saurabh|last4=Montestruque|first4=Luis|date=2009|title=A Tale of Two Synchronizing Clocks|journal=Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems |chapter=A tale of two synchronizing clocks |date=2009|series=SenSys '09|___location=New York, NY, USA|publisher=ACM|pages=239–252|doi=10.1145/1644038.1644062|isbn=9781605585192|s2cid=8242938}}</ref>

===Berkeley algorithm===

{{Main|Berkeley algorithm}}

The Berkeley algorithm is suitable for systems where a [[radio clock]] is not present,. thisThis 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 a 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.<ref>{{Citation |last1=Rentel |first1=Carlos H. |last2=Kunz |first2=Thomas |title= IEEE Wireless Communications and Networking Conference, 2005|chapter=A clock-sampling mutual network time-synchronization algorithm for wireless ad hoc networks |journal=IEEE Wireless Communications and Networking Conference |volume=1 |date=March 2005 |pages=638–644 |publisher=IEEE Press |doi=10.1109/WCNC.2005.1424575|isbn=0-7803-8966-2 |s2cid=1340072 }}</ref>

===Cristian's algorithm===

Line 61:

===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 [[Reliability (computer networking)|unreliable networksnetwork]]s. It can reduce synchronization offsets to times of the order of a few milliseconds over the public Internet, and to sub-millisecond levels over [[Locallocal area network|local area networks]]s.

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

Line 90:

| publisher=IEEE Press

| doi=10.1109/TII.2015.2396003

| bibcode=2015ITII...11..801C

| s2cid=17867070

}}</ref> 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.

Line 100 ⟶ 101:

===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 center]]s 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 10stens of nanoseconds even at high network load.<ref>{{cite book |url=https://www.usenix.org/conference/nsdi18/presentation/geng |title=Exploiting a Natural Network Effect for Scalable, Fine-grained Clock Synchronization|year=2018|pages=81–94|isbn=9781939133014}}</ref> The findings of this research are being tested in financial market applications.<ref>{{cite news |url=https://www.nytimes.com/2018/06/29/technology/computer-networks-speed-nasdaq.html |title=Time Split to the Nanosecond Is Precisely What Wall Street Wants |author=John Markoff |date=June 29, 2018 |work=New York Times}}</ref>

==See also==

Line 110 ⟶ 111:

* [[Time signal]]

* [[Time standard]]

* [[Reference Broadcast Infrastructure Synchronization]]

==References==

Line 122 ⟶ 124:

| last3 = Chan

| first3 = Mun Choon.

| journaltitle = Proceedings of the 2019 ACM Symposium on SDN Research

| titlechapter = Precise Time-synchronization in the Data-Plane Usingusing Programmable Switching ASICs

| journal = Proceedings of the 2019 ACM Symposium on SDN Research

| pages = 8–20

| date = Apr 2019

Line 129 ⟶ 131:

| publisher = ACM

| isbn = 9781450367103

| doi-accesss2cid = free85518997

| doi-access =

}}

* {{citation |title=Exploiting a Natural Network Effect for Scalable, Fine-grained Clock Synchronization |isbn=9781939133014 |url=https://www.usenix.org/conference/nsdi18/presentation/geng |access-date=2021-10-19}}