TY - GEN
T1 - Fundamental limits on synchronization of affine clocks in networks
AU - Freris, Nikolaos M.
AU - Kumar, P. R.
PY - 2007
Y1 - 2007
N2 - We present some impossibility as well as feasibility results on clock synchronization in wireline or wireless networks. We consider a network of n nodes with affine clocks, where one node is taken as a reference, and each other node's clock is described by a skew (relative speedup with respect to the reference clock), and an offset (say) at time 0 with respect to the reference clock. In order to establish impossibility results, we allow for noiseless communication of messages that may contain any information that the transmitting node knows about current or past packets that the node has sent or received. The synchronization problem consists of estimating all the unknown parameters, skews and offsets of all the clocks, as well as the delays of all the communication links. We show that, in general, estimation of all unknown parameters is impossible. We show that all nodal skews, as well as all round trip delays between every pair of nodes, can be estimated correctly. However, the unknown link delays and clock offsets can only be determined up to an (n - 1)-dimensional subspace. Each degree of freedom in this subspace corresponds exactly to the offset of one of the n -1 clocks with respect to the reference node's clock. On the positive side, we show that every transmitting node can predict precisely the time indicated by the receiver's clock at the instant it receives the packet. If we further invoke causality, i.e., that packets cannot be received before they are transmitted, the uncertainty set above can be reduced to a compact polyhedron in ℝn-1, which we describe analytically. We also consider a specific model for delays as the sum of a transmitter-dependent delay, a receiver-dependent delay and a propagation delay where the latter is known. We identify conditions on the transmission and reception delays, for which estimation admits a unique solution.
AB - We present some impossibility as well as feasibility results on clock synchronization in wireline or wireless networks. We consider a network of n nodes with affine clocks, where one node is taken as a reference, and each other node's clock is described by a skew (relative speedup with respect to the reference clock), and an offset (say) at time 0 with respect to the reference clock. In order to establish impossibility results, we allow for noiseless communication of messages that may contain any information that the transmitting node knows about current or past packets that the node has sent or received. The synchronization problem consists of estimating all the unknown parameters, skews and offsets of all the clocks, as well as the delays of all the communication links. We show that, in general, estimation of all unknown parameters is impossible. We show that all nodal skews, as well as all round trip delays between every pair of nodes, can be estimated correctly. However, the unknown link delays and clock offsets can only be determined up to an (n - 1)-dimensional subspace. Each degree of freedom in this subspace corresponds exactly to the offset of one of the n -1 clocks with respect to the reference node's clock. On the positive side, we show that every transmitting node can predict precisely the time indicated by the receiver's clock at the instant it receives the packet. If we further invoke causality, i.e., that packets cannot be received before they are transmitted, the uncertainty set above can be reduced to a compact polyhedron in ℝn-1, which we describe analytically. We also consider a specific model for delays as the sum of a transmitter-dependent delay, a receiver-dependent delay and a propagation delay where the latter is known. We identify conditions on the transmission and reception delays, for which estimation admits a unique solution.
UR - http://www.scopus.com/inward/record.url?scp=62749133564&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=62749133564&partnerID=8YFLogxK
U2 - 10.1109/CDC.2007.4434546
DO - 10.1109/CDC.2007.4434546
M3 - Conference contribution
AN - SCOPUS:62749133564
SN - 1424414989
SN - 9781424414987
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 921
EP - 926
BT - Proceedings of the 46th IEEE Conference on Decision and Control 2007, CDC
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 46th IEEE Conference on Decision and Control 2007, CDC
Y2 - 12 December 2007 through 14 December 2007
ER -