Fundamental limits on synchronizing clocks over networks

Nikolaos M. Freris, Scott R. Graham, P. R. Kumar

Research output: Contribution to journalArticlepeer-review

Abstract

We characterize what is feasible concerning clock synchronization in wireline or wireless networks. We consider a network of n nodes, equipped with affine clocks relative to a designated clock that exchange packets subject to link delays. Determining all unknown parameters, i.e., skews and offsets of all the clocks as well as the delays of all the communication links, is impossible. All nodal skews, as well as all round-trip delays between every pair of nodes, can be determined correctly. Also, every transmitting node can predict precisely the time indicated by the receiver's clock at which it receives the packet. However, the vector of unknown link delays and clock offsets can only be determined up to an (n-1)-dimensional subspace, with each degree of freedom corresponding to the offset of one of the (n-1) clocks. Invoking causality, that packets cannot be received before they are transmitted, the uncertainty set can be reduced to a polyhedron. We also investigate structured models for link delays as the sum of a transmitter-dependent delay, a receiver-dependent delay, and a known propagation delay, and identify conditions which permit a unique solution, and conditions under which the number of the residual degrees of freedom is independent of the network size. For receiver-receiver synchronization, where only receipt times are available, but no time-stamping is done by the sender, all nodal skews can still be determined, but delay differences between neighboring communication links with a common sender can only be characterized up to an affine transformation of the (n-1) unknown offsets. Moreover, causality does not help reduce the uncertainty set.

Original languageEnglish (US)
Article number5605654
Pages (from-to)1352-1364
Number of pages13
JournalIEEE Transactions on Automatic Control
Volume56
Issue number6
DOIs
StatePublished - Jun 2011

Keywords

  • Clock offsets
  • clock skews
  • clock synchronization
  • delays
  • networked control
  • scheduling
  • sensor networks

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Fundamental limits on synchronizing clocks over networks'. Together they form a unique fingerprint.

Cite this