(2023-04-09) On reliable timekeeping on slow networks
-----------------------------------------------------
I am very passionate about timekeeping. I have a nice collection of watches,
some of which are capable of syncing via longwaves or even Bluetooth LE, and
the protocol to do this already is reverse-engineered, at least to the
extent of performing basic time synchronization tasks ([1]). I'll probably
write a non-GUI tool for it as well once I figure out what the most optimal
stack is to write it on top of. But, of course, these tools also need some
source of truth. Something needs to set the time on our own client devices
before we can pass it further or display it to the user.

Nowadays, all time synchronization and coordination over the Internet is
usually done via the NTP protocol. It's really well-engineered and takes
into account a lot of factors and allows to receive accurate time all over
the world. Can't really complain about that. One thing I can complain about
though, is that it's too complex to reimplement from scratch, and some CVE
reports about NTP server or client vulnerabilities just confirm that. On top
of that, it involves a lot of overhead data in every synchronization packet,
which might not be a lot in modern conventional networks, but pose a
significant problem once we're talking about something like GPRS at 30 Kpbs,
PSTN or CSD dialup at 9600 bps, AX.25 at 1200 bps or even slower
transmission modes at 300 bps. In these conditions, every extra byte
matters. The solution? Ye goode olde Time protocol (RFC 868), which some
timekeeping networks (like time.nist.gov) still gracefully run on the port
37 of their servers. It returns a 4-byte (32-bit) timestamp on a TCP
connection or as a response to any UDP datagram, and that's it. The
timestamp is expected to represent the number of seconds since the beginning
of the year 1900 UTC, and is supposed to roll over every 136 years.

Now, I encourage you to only use the UDP mode of this protocol whenever you
need it, as TCP connections made to just retrieve a 4-byte payload both pose
significant overhead for our purposes and don't make server admins happy
either. And, just like with NTP, you still need some way to measure elapsed
time locally with around a millisecond precision. Once it is sorted though,
the algorithm to get more or less accurate time (although with a whole
second resolution) is very simple and straightforward:

1. Prepare a tool for time measurement of steps 2 and 3 combined.
2. Send a random 32-bit datagram to the Time server.
3. Receive the 32-bit timestamp datagram FTIME from the Time server.
4. Record the execution time (in milliseconds) of steps 2 and 3 as ETIME.
5. Obtain the true Unix timestamp (in seconds) using the following formula:
  TRUETIME = |(1000*FTIME + ETIME/2 - 2208988799500) / 1000|
6. Emit the TRUETIME value for further processing. End of algorithm.

There is a couple of things that might need explanation here. First, the RFC
says the Time protocol expects an empty datagram in UDP mode, but IRL most,
if not all, implementations accept any datagram and just discard its
contents. The 4-byte length of the outgoing datagram was chosen to make the
resulting IP packet have exactly the same length as the one we're going to
receive, so we can then safely divide the elapsed time by 2 to get more or
less accurate correction. Second, the constant 2208988799500 is the number
of milliseconds between the start of the year 1900 (where Time protocol
timestamps start) and the start of the year 1970 (where the Unix epoch
starts), minus 500 milliseconds used for rounding the final result properly.
So, starting with the year 2036 when the 32-bit Time protocol counter rolls
over, we will be adding 2082758400500 here instead of subtracting
2208988799500. And this is something that we need to know before applying
the formula, but I hope no one will ever finds themselves in the situation
they don't know whether or not the year 2036 already has come. But just in
case, here is a more future-proof version of the same algorithm with a
larger safety margin (until the year 2106):

1. Prepare a tool for time measurement of steps 2 and 3 combined.
2. Send a random 32-bit datagram to the Time server.
3. Receive the 32-bit timestamp datagram FTIME from the Time server.
4. Record the execution time (in milliseconds) of steps 2 and 3 as ETIME.
5. Obtain the true Unix timestamp (in seconds) using the following formula:
  TRUETIME =
    |(1000*FTIME + ETIME/2 - 2208988799500) / 1000| if FTIME > 2208988800,
    |(1000*FTIME + ETIME/2 + 2082758400500) / 1000| otherwise.
6. Emit the TRUETIME value for further processing. End of algorithm.

Somewhere between the year 2036 and 2106, you can switch to using the second
formula unconditionally, and this will prolong the algorithm to the year
2172. Afterwards, you adjust the offset accordingly (500 + the amount of
milliseconds that actually passed between the start of 1970 and the start of
2172), and so on. This way, the 32-bit second counter can be reused forever.

This approach has the following advantages: only a single send-receive round
required, no transactional overhead thanks to UDP (4 bytes out, 4 bytes in),
not having to rely on the local clock for anything but elapsed time
measurement, and simple but accurate enough compensation for the roundtrip
time. For really slow networks, I can't think of anything better at the
moment. This is why I hope that even when NIST stops serving time using this
protocol, someone still will. Maybe, I'll set it up right here on hoi.st,
who knows.

--- Luxferre ---

[1]: https://git.sr.ht/~luxferre/RCVD

You are viewing proxied material from hoi.st. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.