When I started my PhD, one of the first papers I read was *On Maximum Likelihood Estimation of Clock Offset* by Daniel Jeske [1] from University of California, Riverside. It eventually set the direction of my future research and ultimately my PhD dissertation. I found this paper quite interesting as it talked about the estimation of clock phase offset. Later I went on to explore what was missing here (the clock frequency offset) and more.

Carrier phase estimation is a different problem that has already been discussed in the past here, here and here. Most of the solutions involve a Phase Locked Loop (PLL) from a software defined radio perspective. In this article, I summarize the main idea of clock offset estimation in simple words.

## What is a Timestamp?

The timer in a typical embedded device consists of a counter and a register. Driven by an oscillator, the value of the counter increments or decrements at regular intervals.

- An increment counter typically starts at 0x0…00. When this counter reaches the maximum value of 0xF…FF, it overflows to 0x0…00 and starts counting again.
- On the other hand, a decrement counter typically starts at 0xF…FF. When this counter reaches the minimum value of 0x0…00, it underflows to 0xF…FF and resets the process.

At any instant, e.g., a message arrival event driven by a Rx start interrupt, the value of the counter can be captured and stored in a register that can be later accessed to find the time of that event – according to the node’s own reference clock.

As an example, consider the figure below where

- the timestamp value is captured in Register
- the Counter is an incremental counter
- Tx Start is an event that resets the counter, and
- Rx Start is an event that captures the Counter value to Register.

## Timing Exchange

Assume that two nodes exchange above timestamps with each other through the wireless medium as shown in the figure below.

The distance between the two nodes is $R$ while the time of flight from one node to another is $\tau$. Consequently,

$$R = \tau \cdot c$$

We denote the real time by $t$, Node A’s time by $T_A$ and Node B’s time by $T_B$. Since each node starts at a random time, there is a clock offset between its time as compared to the real time. Let us denote the time offset of Node A as $\phi_A$ while that of of Node B as $\phi_B$.

$$T_A = t + \phi_A$$

$$T_B = t + \phi_B$$

Refer to the next figure to observe how the chain of events unfolds.

The timestamp exchange process is as follows.

- Node A sends its local timestamp $T_1$ to Node B at real time $t_1$, where
- Node B receives this packet at real time $t_2$ and records its local time $T_2$, where
$$T_2 =t_2 + \phi_B$$

Clearly,

$$t_2 = t_1 + \tau,\qquad or \qquad \tau = t_2-t_1$$

Therefore, we can write

\[

U = T_2-T_1 = t_2 +\phi_B- t_1-\phi_A

\]With $\tau$ as defined above, this can be written as

\[

U = \tau +\phi

\]where $\phi=\phi_B-\phi_A$ is the clock offset between the two nodes.

- After a processing delay, Node B sends its local timestamp $T_3$ at real time $t_3$ to Node A.
- Node A records it at $T_4$ at actual time $t_4$. Since $t_4 = t_3+\tau$,
\[

V = T_4 -T_3 = t_4+\phi_A – t_3 – \phi_B

\]Again, the above expression can be written as

\[

V = \tau ~-~ \phi

\]Next we turn towards the delay distribution encountered in real situations.

## Delay Distribution

The above equations were for an ideal scenario of a deterministic clock offset only. In practice, any timing exchange involves random delays that can be incorporated in the above equations as

$$\begin{equation}

\begin{aligned}

U_i ~&=~ \tau + \phi + X_i \\

V_i ~&=~ \tau \,-\, \phi + Y_i

\end{aligned}

\end{equation}\label{equation-model}$$where $X_i$ and $Y_i$ are random delays in the forward and reverse directions, respectively. In the paper, these are modeled as coming from an exponential distribution with mean $\lambda$. This makes sense because delays are never negative. The probability distribution function (pdf) of an exponential random variable is defined as

\[

\nonumber f(x) = \left\{

\begin{array}{l l}

\lambda e^{-\lambda x} & \quad x > 0\\

0 & \quad \textrm{otherwise}

\end{array} \right.

\]With the unit step function defined as

\[

\nonumber u(x) = \left\{

\begin{array}{l l}

1 & \quad x \geq 0\\

0 & \quad \textrm{otherwise}

\end{array} \right.

\]the pdf can be written concisely as

\[

f(x)= \lambda e^{-\lambda x} u(x)

\]Now a maximum likelihood estimate for this delay distribution can be found as follows.

## Maximum Likelihood Estimation

Based on the set of $N$ observations $U_i$ and $V_i$ in Eq (\ref{equation-model}), the likelihood function can be written as

\[

L(\tau,\phi) = \lambda^{2N} e^{-\lambda \left( \sum_{i=1}^N U_i + \sum_{i=1}^N V_i- 2N\tau\right)}\cdot u\left(U_{(1)}\ge \tau + \phi~;~ V_{(1)}\ge \tau – \phi\right)

\]where $U_{(1)}$ denotes the minimum value among the observations $U_i$ and $V_{(1)}$ is defined in a similar manner. The terms in the unit step function arise from the respective definitions of $U_i$ and $V_i$ before and the positive nature of the exponential distribution. These two conditions define the region in which likelihood function exists.

\[

\begin{aligned}

\phi &\le -\tau + U_{(1)}\\

\phi &\ge +\tau \,-\, V_{(1)}

\end{aligned}

\]This is shown in the figure below.

Without going into more details (e.g., considering the signs of $U_{(1)}$ and $V_{(1)}$), we can simply infer from the likelihood function that it attains a maximum at the largest value of $\tau$ (as it appears in the exponential of the likelihood function). From the above figure, this is achieved at the right corner of the triangle: at the intersection of the two lines.

\[

-\tau + U_{(1)} = \tau \,-\, V_{(1)}

\]This intersection yields the maximum likelihood estimate of delay as

\[

\hat \tau = \frac{ U_{(1)} + V_{(1)}}{2}

\]By plugging this value back in any one of those equations, we get the maximum likelihood estimate of the clock offset as

\[

\hat \phi = \frac{ U_{(1)} – V_{(1)}}{2}

\]Interestingly, this is the same expression suggested in [2] by informal arguments and empirical observations. This beautiful geometrical derivation kept me interested in exploring the field of synchronization in significant depths during and after my PhD years.

### References

[1] D. Jeske,

*On Maximum Likelihood Estimation of Clock Offset*, IEEE Transactions on Communications, Vol. 53, No. 1, Jan 2005.

[2] V. Paxson,*On Calibrating Measurements of Packet Transit Times*,” Proc. 7th ACM Sigmetrics Conference, Vol. 26, Jun 1998.

$$T_1 = t_1 + \phi_A$$