[gpsd-dev] Time autonomy

[Eric S. Raymond]

This is not a goal for the next release, it's a longer-term direction.
The time-service nuts should pick over it, criticize, and improve.

----------------------------------------------------------------------

This is a proposed way to handle the era-detection problem that is
intended to make it possible for GPSD to be time-autonomous - that is, 
not have to rely on the host system clock or NTP time.

This is me engineering for the SBC-a-thousand-miles-at-sea case.
Besides, if we're going to take the role of feeding NTP seriously,
it's circular to rely on NTP.

For purposes of this dicussion, WEEK is 7 * 24 * 60 *60 and
ROLLOVER_PERIOD is your GPS's era length in seconds.  It is presently
1024 * WEEK (10 bit week counter); your device may optionally tell you
it's 8192 * WEEK (13-bit week counter).

1. Compile the century and GPS week of the current build time into
   GPSD as two constants, BUILD_CENTURY and BUILD_WEEK. Compile in the
   date of the last rollover as BUILD_EPOCH. Compile in the leapsecond
   offset as BUILD_LEAPSECONDS. With these, initialize four variables:
   saved_century, saved_week, saved_epoch, and leap_offset.

2. Update leap_offset as the device makes it available.  For purposes
   of later discussion, the "leap residual" at any given time is the
   unknown difference between the current actual leap offset and our
   saved leap_offset.  The difference will be > 0 if the device's
   almanac is stale and a leap-second update has occurred since it was
   last updated.  We will say that time is "nearly correct" if the
   time error is bounded by the leap residual.

3. When an NMEA device gives you a UTC time/date t, apply the saved
   century if it has only a two-digit year.  Then compute from that
   time as follows

   week = (t + leap_offset - saved_epoch) / WEEK
   tow = (t + leap_offset - saved_epoch) % WEEK

   A binary device will give you (week, tow) directly.

3. You now have a (week, tow) pair. If week < saved_week, increment
   saved_epoch by ROLLOVER_PERIOD, then copy week into saved_week.

4. This is the only step at which you may choose to trust the system clock.
   If you do, repeatedly add ROLLOVER_PERIOD until the computed time is in
   the future.  Then subtract it once.

5. Now report GPS time as :

        t = saved_epoch + week * WEEK + tow - leap_offset.

   Save the computed century in saved_century.

This will yield nearly correct time provided either (a) you trust the
system clock, or (b) the device is on continuously from a date during
its build era (e.g. before the first rollover after BUILD_EPOCH), and
gets at least one valid fix per week.  (There are optimistic scenarios
in which fix frequency can drop to once per *era* without worrying
edge cases.)

To upgrade so the algorithm can handle shutdown periods without
trusting the system clock, add two steps:

1a. If /var/run/gps-epoch exists, initialize saved_epoch from it at
startup time.

6. If you had to increment saved_epoch in step 3, write it
/var/run/gps-epoch at shutdown time.

Note that you are guaranteed nearly correct time for one full era from
BUILD_EPOCH (a minimum of 19 years) even if you cannot write
/var/run/gps-epoch.  If you can write it, you get nearly correct time
forever (or until various quantities overflow, anyway).

There is one odd case: if NMEA device time is not correctly
leap-second compensated (e.g. because the device's almanac is stale),
there is a tiny window equal to the leap second residual, just before
midnight of a new rollover period, during which it will compute (week,
tow) incorrectly.

There are some obvious complications when dealing with the 13-bit week
counters intended to be introduced by the Block III birds.

-- 
                <a href="http://www.catb.org/~esr/";>Eric S. Raymond</a>

Of all tyrannies, a tyranny exercised for the good of its victims may
be the most oppressive. It may be better to live under robber barons
than under omnipotent moral busybodies. The robber baron's cruelty may
sometimes sleep, his cupidity may at some point be satiated; but those
who torment us for our own good will torment us without end, for they
do so with the approval of their consciences.
        -- C. S. Lewis