Warmup mode done -- here's what's left

Posted on June 4, 2016

I’ve finished all the estimators for the warmup phase of the RADclock algorithm. What’s left is:

The normal-mode estimators are similar to the warmup mode estimators (except with some added complexity; there’s level shift detection, for example, to robustly detect if the RTT to the server has increased). I have written higher-order functions and per-packet functions that let me concisely write the estimators in an order of magnitude fewer lines as the original C version – so writing the normal-mode estimators is not likely to pose much of a challenge.

I’ve also written a list type1 to store historical data points that is equivalent to RADclock’s sync_hist ring buffer along with a tiny DSL to describe points (and therefore intervals) in a history list. There is a terrifying quantity of arithmetic on indices and pointers in sync_bidir.c and my types allow me to avoid it entirely – instead I can write incredibly simple expressions to specify which ranges of points are passed to my estimators. Furthermore, the functions that generate those ranges are independent from any calculations – this lets me verify that the right points are worked on and that all the needed data points are available without having to run any of the actual estimating code. I need to write code to manage the top-level windows that determines which samples are kept and which are expired but that isn’t difficult – all that needs to be done is figure out closed-form expressions for window ranges from the RADclock imperative C code that manages the relevant indices.

Kitsu Chiri was right.

Kitsu Chiri was right.2

NTP, unfortunately, uses the UTC timescale and not (TAI, leapoffset)3 to transmit time, and to create a reliable NTP client implementation, code needs to be written to robustly deal with the horrid discontinuities and repeated time values that are caused by a leap second event – and to not interpret those values and the subsequent 1-second offset as errors or invalid data or a change that must be corrected by the timing algorithms. RADclock has code that attempts to do this which I haven’t yet analyzed.

Semi-relatedly, Darryl Veitch, one of the creators of RADclock – the superb NTP implementation that I am basing my work on, did a first-of-its-kind analysis of public NTP Stratum 1 server replies during the 2015 leap second event (compared against a RADclock instance and independently measured with a GPS-synchronized precision network capture card) and demonstrated widespread4 erroneous/noncompliant behaviour related to the leap second event.

Finally, I need to figure out how to properly select and access a counter register under Xen – RDTSC is not necessarily the right choice and if it isn’t there alternatives like HPET and the ACPI PM timer. I also need to figure out how to get a counter register on ARM systems. Right now for testing I just have an extremely simple stub that calls RDTSC but this is not appropriate for production use.

Also (and less importantly) I need to figure out a name for this NTP implementation – if anyone has suggestions feel free to email me / comment on github / tweet at me.

  1. I’ve only informally tested my list type – but once I get around to reading how to test monadic code with quickcheck I will write an algebraic specification of my data type and quickcheck code to test my type against it.

  2. Image is from page 3 of chapter 166 of さよなら絶望先生, translated by Suimasen Scans

  3. GPS, Galileo, BeiDou, and PTP all use (TAI, leapoffset) as a time format – the designers of the NTP protocol messed up and should have done so as well. PTP / IEEE 1588 is a protocol used to transmit time from a master source (such as a GPS receiver or an atomic clock) over Ethernet wiring and with specialized timestamping network interfaces that achieves much higher performance than NTP. It is used in industrial applications such as power grid synchronization / measurement, control/data acquisition timing in large scientific projects (such as the LHC) or in test aircraft. Discontinuities in time, repeated time values, and changes in frequency (“leap smear” is not an acceptable solution for any sort of application that requires high-precision timing/frequency reference) as are caused by leap second events in UTC, are never acceptable in such applications – so PTP uses TAI as its timescale. To let users synthesize UTC time if needed, along with the current TAI time (which is pure and clean and discontinuity-free) PTP master clocks transmit a special field called “currentUtcOffset” – the number of leap seconds so far.

  4. Only 61% of the measured servers did not return erroneous or noncompliant data during the leap second event. This is an unacceptable state of affairs and blame should be placed entirely on the NTP standard and not the implementers. djb has the right approach here – if a standard leaves many ways to mess up an implementation (and those traps can be removed), the standard is broken. Modern cryptographic engineering shows that the road to trustworthy and secure systems is paved with simple standards that as are free from deadly edge cases as possible. Every leap second event reminds us that the NTP standard is in flagrant opposition to this principle.