clock deltas

Clock Delta Problem

Suppose you have two computers on different networks with the following assumptions

Each computer has a system time which may be different from the other, but this offset is constant. Let $t_{c}, t_{c}$ be the client and server time, then there exists some $Δ_{c}$ such that $t_{c} + Δ_{c} \approx t_{s}$
Each computer clock advances forward at the same rate
The travel time from the client to server denoted by $\vec{c s}$ and $\vec{s c}$ respectively, and there exists some $Δ_{t}$ such that $\vec{c s} + Δ_{t} \approx \vec{s c}$

In the clock delta problem, you do not know the value of

Δ_{t}

nor

Δ_{c}

, and you must design a program which estimates these values. The program may send packets over the network with any required information.

The reason for $Δ_{t}$ is that the travel time from client to server is always the same and the travel time from the server to client is always the same, but the two times my differ (different packet routing).

Time Conversion Function

Suppose that

t_{c}, t_{s}

are times measured on the client and server clock respectively, then to convert the time

t_{c}

to the servers time one has to compute

t_{c} + Δ_{t}

and to convert a server time to client time one has to compute

t_{s} - Δ_{t}

This follows directly from the definition of the clock delta problem as

t_{c} + Δ_{t} = t_{s}

The above corollary is important because we cannot measure the elapsed time unless two times are measured on the same clock.

Elapsed Time

Suppose that

t_{1}, t_{2} \in R^{\geq 0}

are two times measured on the same clock , then the amount of time between the two is given by

| t_{2} - t_{1} |

Note that if $t_{1} \leq t_{2}$ this equation is simply $t_{2} - t_{1}$

Isolating for Travel Time and Clock Delta From Packets

Suppose that a packet is sent from the client to the server it is sent at client time

c_{1}

and received at server time

s_{1}

, after a slight delay it sent back from the server at time

s_{2}

and received on the client at client time

c_{2}

then

Δ_{c} = \frac{(s_{1} - c_{1}) - (c_{2} - s_{2}) + Δ_{t}}{2}

and

Δ_{t} = (c_{2} - s_{2}) - (s_{1} - c_{1}) + 2 Δ_{c}

Since the travel time from client to server and server to client is constant, then we know that $\vec{c s}$ is the amount of elapsed time from the moment the packet was sent and received, as measured on the clients clock the initial send time is $c_{1}$ and the received time was $s_{1}$ as measured on the servers clock, therefore the time that $c_{1}$ was sent on the servers clock is given by $c_{1} + Δ_{c}$ therefore the elapsed time during travel is given by $\vec{c s} = s_{1} - (c_{1} + Δ_{c}) = s_{1} - c_{1} - Δ_{c}$ Note that the absolute values are omitted because when measured on the the same clock, the time that a packet is sent comes before when a packet is received.

Similarly we can deduce that $\vec{s c} = c_{2} - (s_{2} - Δ_{c}) = c_{2} - s_{2} + Δ_{c}$ Since we know that $\vec{c s} + Δ_{t} = \vec{s c}$ then we can deduce that $s_{1} - c_{1} - Δ_{c} + Δ_{t} = c_{2} - s_{2} + Δ_{c}$ therefore $Δ_{c} = \frac{(s_{1} - c_{1}) - (c_{2} - s_{2}) + Δ_{t}}{2}$ and $Δ_{t} = (c_{2} - s_{2}) - (s_{1} - c_{1}) + 2 Δ_{c}$

The above proposition is good, but we can't isolate exactly $Δ_{c}$ or $Δ_{t}$ we need one to compute the other. This is when approximations start to come in, we will build up an approximation of the travel and clock delta. For each of the symbols we've mentioned let the same symbol above it with a bar represent the approximation of it, for example $\overset{―}{Δ_{c}}$ is the approximation of $Δ_{c}$ , additionally this process will be iterative, and so we'll denote the approximation after the $i$ -th update as $\overset{―}{Δ_{c}^{i}}$

In order to make this process tractable, we'll start by assuming that $\overset{―}{Δ_{t}^{0}} = 0$ which is not a horrible assumption to make, which allows us to compute that $\overset{―}{Δ_{c}^{0}} = \frac{(s_{1} - c_{1}) - (c_{2} - s_{2}) + 0}{2}$

But the above equation also has some problems too, recall that $c_{1}, s_{1}, s_{2}, c_{2}$ is just a sampling of a single full pass, and since we are now on the live network there is going to be variance between any two different passes. In order to account for this, we'll average out the values in question, to kickstart this process we'll need better variables, so let $c_{s}^{i}, s_{r}^{i}, s_{s}^{i}, c_{r}^{i}$ denote the $i$ -th client send, server receive, server send, and client receive times all on their own clocks respectively.

With that in place, we set up the following system, the client starts by sending a packet with its current time to the server, this is the "send time" denoted by $c_{s}^{0}$ then the server receives the packet and gets the time which is denoted by $s_{r}^{0}$ , then the sever waits for some fixed time duration which we wil denoted by $w$ and measured in seconds (to slow down the frequency of the ping/pong) and gets a new time, which is denoted by $s_{s}^{0}$ and sends $(s_{r}^{0}, s_{s}^{0})$ to the client.

When received the client stores the value $c_{r}^{0}$ somewhere and then puts the value $s_{r}^{0} - c_{s}^{0}$ into a ring buffer which we will denote by $R B_{c \to s}$ which represents the a collection of time differences between the client send and server receive, note that the values stored are not actually the travel time from the client to the server because the two times are not measured on the same clock.

$R B_{c \to s}$ will have some fixed size which we will assume to be $1000$ , additionally there will is another ring buffer $R B_{s \to c}$ of the same size in which will store $c_{r}^{0} - s_{s}^{0}$ . To simplify things we make the behavior of the server identical to that of the client, the benefit being that it spreads out the work-load between two computers meaning twice the number of iterations can be done in the same time.

For clarity after the value is added to the ring buffer the client then waits for $w$ seconds and then measures $c_{s}^{1}$ and sends $(c_{r}^{0}, c_{s}^{1})$ to the server, then the server adds $c_{r}^{0} - s_{s}^{0}$ and the process restarts. The ping and the pong continues until the ring buffers are full, which will first occur on the client because the server only starts adding to the ring buffer after its first receive, which occurs after the clients first receive.

Once the ring buffers are full, we take the average of the ring buffers, on the client when we take the average of $R B_{c \to s}$ it is given by this equation: $\overset{―}{s_{r} - c_{s}} : = \frac{\sum_{i = 0}^{999} (s_{r}^{m + i} - c_{s}^{m + i})}{1000}$ and $\overset{―}{c_{r} - s_{s}} : = \frac{\sum_{i = 0}^{999} (c_{r}^{m + i} - s_{s}^{m + i})}{1000}$ for some $m \in N_{0}$ , the purpose of $m$ is to just denote that the index may not start at $0$ because after more than $1000$ client receives the ring buffer removes some of the beginning elements.

Now looking back to our initial value for $\overset{―}{Δ_{c}^{0}}$ we will use these averaged values instead to say that $\overset{―}{Δ_{c}^{0}} = \frac{(\overset{―}{s_{r} - c_{s}}) - (\overset{―}{c_{r} - s_{s}}) + 0}{2}$ which will help with the variance between individual network send and receive events.

Now that we've computed an initial value for $\overset{―}{Δ_{c}^{0}}$ we can use this to come up with an expected arrival time for the next packet we send to the server. Right before we send the packet, we get our current time

Now that we know $\overset{―}{Δ_{c}^{0}}$ we can compute $\overset{―}{Δ_{t}^{1}} = \overset{―}{c_{r} - s_{s}} - \overset{―}{s_{r} - c_{s}} + 2 \overset{―}{Δ_{c}^{0}}$ The order of computation will be $\overset{―}{Δ_{t}^{0}} \to \overset{―}{Δ_{c}^{0}} \to \overset{―}{Δ_{t}^{1}} \to \overset{―}{Δ_{c}^{1}} \dots$ and so on each iteration we will first compute $Δ_{t}^{i}$ and then use that to compute $Δ_{c}^{i}$ .

Now that the process has been bootstrapped we will continue updating our ring buffers so that $\overset{―}{c_{r} - s_{s}}, \overset{―}{s_{r} - c_{s}}$ are still a smoothed version of the current travel times, and at each iteration we first compute

🏗️ ΘρϵηΠατπ🚧 (under construction)

🏗️ $Θ ρ ϵ η Π α τ π$ 🚧 (under construction)