End-of-cycle detection solves the buffering problem.

1 files changed, 0 insertions, 250 deletions

diff --git a/www/hacking.html b/www/hacking.html
index eda4a90b..d15724ea 100644
--- a/www/hacking.html
+++ b/www/hacking.html
@@ -1136,256 +1136,6 @@ logfile format.</p>
 portion during which the GPS has no fix, a portion during which it has
 a fix but is stationary, and a portion during which it is moving.</p>
 
-<h1 id="buffering">The buffering problem</h1>
-
-<p>Considered in the abstract, the cleanest thing for a
-position/velocity/time oracle to return is a 14-tuple including
-position components in all four dimensions, velocity in three, and
-associated error estimates for all seven degrees of freedom.  This is
-what the O message in GPSD protocol attempts to deliver.</p>
-
-<p>If GPS hardware were ideally designed, we'd get exactly one report
-like this per cycle from our device. That's what we get from the SiRF
-(packet type 02), Zodiac (packet type 1000), Garmin Binary, and iTalk
-(NAV_FIX message) protocols. Garmin and Trimble also implement full
-TPV solutions in a single line of text. These, together, account for
-a share of the GPS market that is 80% and rising in 2006.</p>
-
-<p>Unfortunately, many GPSes actually deliver their TPV reports as a
-collection of sentences in NMEA 0183 (or as packets in a vendor binary
-protocol less well designed than SiRF's) each of which is only a
-partial report.  Here's the most important kind of incompleteness: for
-historical reasons, NMEA splits 2-D position info and altitude into
-two different messages (GGA and GPRMC or GLL), each issued once during
-the normal 1-second send cycle.</p>
-
-<h2 id="mapping">Mapping the design space</h2>
-
-<p>For NMEA devices, then (and for devices speaking similarly mal-designed
-vendor binary protocols) accumulating a complete TPV thus requires
-decisions about the following sorts of actions:</p>
-
-<ol>
-<li>What data will be buffered, and for how long.</li>
-
-<li>When the accumulated data will be shipped to the user.</li>
-
-<li>When to invalidate some or all of the buffered data.</li>
-
-<li>The when-to-ship question assumes watcher mode is on; if the user
-queries explicitly the when-to-ship decision is out of our hands.</li>
-</ol>
-
-<p>In thinking about these decisions, it's useful to consider the set of
-events on which an action like "merge new data into TPV buffer" or
-"clear the TPV data buffer" or "ship report to user" can trigger.</p>
-
-<ol>
-<li>On receipt of any sentence or packet from the GPS.</li>
-
-<li>On receipt of a specified sentence or packet from the GPS.</li>
-
-<li>When the timestamp of a sentence or packet differs from the 
-   last timestamp recorded.</li>
-
-<li>When some or all of the TPV data has not been refreshed for a
-   specified number of seconds.</li>
-</ol>
-
-<p>That latency can really matter.  If the GPS is on a car driving down
-the highway at 112kph (70mph), the 1 second delay in the buffered data
-can represent an error of 31 meters (102 feet) in reported position.</p>
-
-<p>In general, buffering would make it easy to retrieve the data you want
-at the time you want it, but the data would not necessarily be valid
-for time of retrieval.  Buffering makes life easier for applications that
-just want to display a position indicator, and harder for
-perfectionists that worry about precise location of moving GPSes.</p>
-
-<p>The policy decision about whether you want to be a "perfectionist"
-or not fundamentally belongs in the client.  This isn't to say
-<code>gpsd</code> could not have different buffering modes to help the
-client implement its decision, but the modes and their controls would
-have to be implemented <em>very</em> carefully.  Otherwise we'd risk
-imposing the wrong policy (or, worse, a <em>broken version</em> of a
-wrong policy) on half the client applications out there.
-
-<p>There are hundreds, even thousands of possible sets of action-to-event
-bindings.  The "right" binding for a particular device depends not
-only on the protocol it uses but on considerations like how much time
-latency we are willing to let the buffering policy inflict on a
-report.</p>
-
-<p>Discussion of possible policies follows.  See also the speculation 
-later on about combining buffering with interpolation.</p>
-
-<h3 id="rtcpp">Report then clear per packet</h3>
-
-<p>A device like a SiRF-II that reports all its TPV data in a single
-packet needs no buffering; it should ship to the user on receipt of
-that packet and then invalidate the TPV buffer right afterwards.
-(This is a "report then clear per packet" policy.)</p>
-
-<p>But triggering a buffer clear on every packet would do bad things if 
-we're in client-pull mode. We never know when a client might ask for a
-response.  Consider the case of two simultaneously connected clients,
-one sending queries and the other in watcher mode - if we clear after
-we ship the O message to the watcher, then the other client queries,
-it gets nothing in response.</p>
-
-<h3 id="bartcot">Buffer all, report then clear on trigger</h3>
-
-<p>On the other hand, if (say) we knew that an NMEA GPS were always going
-to end its report cycle with GPGGA, it might make sense to buffer 
-all data until GPGGA appears, ship a report afterwards, and then
-clear the TPV buffer.  This would mean shipping just one report 
-per cycle (good) at the cost of introducing some latency into the
-reporting of data the GPS sends earlier in the cycle (bad).  (This
-would be "buffer all, report-then-clear on trigger")</p>
-
-<p>Here's where it gets ugly.  We don't know what the user's tolerance
-for latency is.  And, in general, we can't tell when end-of-cycle, is
-happening, because different NMEA devices ship their sentences in
-different orders.  Worse: we can't even count on all send cycles of
-the same device having the same end sentence, so the naive plan of
-waiting one cycle to see what the end sentence is won't work. Devices
-like the Garmin 48 have two different cycle sequences with different
-start and end sentences.</p>
-
-<p>So we can't actually trigger on end-of-cycle.  The only
-between-cycles transition we can spot more or less reliably is
-actually <em>start</em> of cycle, by looking to see when the timestamp
-of a sentence or packet differs from the last timestamp recorded
-(event 3 above).  This will be after the last end-of-cycle by some
-(possibly large) fraction of a second; in fact, waiting for
-start-of-cycle to report data from the last one is the worst possible
-latency hit.</p>
-
-<h3 id="baroepcasoc">Buffer all, report on every packet, clear at start-of-cycle</h3>
-
-<p>Another possible policy is "buffer all, report on every packet, clear
-at start-of-cycle".  This is simple and adds minimum reporting
-latency to new data, but means that O responses can issue more than once per
-second with accumulating sets of data that only sum up to a complete
-report on the last one.</p>
-
-<p>Another advantage of this policy is that when applied to a device like 
-a SiRF-II or Zodiac chipset that ships only one TPV packet per cycle,
-it collapses to "report then clear per packet".</p>
-
-<p>Here's a disadvantage: the client display, unless it does its own
-buffering, may flicker annoyingly.  The problem is this: suppose we
-get an altitude in a GGA packet, throw an O response at the client,
-and display it.  This happens to be late in the report cycle.  Start
-of cycle clears the buffer; a GPRMC arrives with no altitude in it.
-The altitude value in the client display flickers to "not available",
-and won't be restored until the following GGA.</p>
-
-<p>This is the policy gpsd currently follows when J=0 (the default).</p>
-
-<h3 id="baroencd">Buffer all, report on every packet, never clear data</h3>
-
-<p>Has all the advantages of the previous policy and avoids the flicker 
-problem.  However, it would mean the user often sees data that is up to one 
-cycle time stale.  This might be OK except that it could happen even if
-the GPS has just lost lock &mdash; that is, in the interval between start
-of cycle and receipt of sentence with the mode field invalidating the,
-bad data, gpsd would be pretending to know something it doesn't.</p>
-
-<p>GPSes sometimes do this, delivering data from dead-reckoning or
-interpolation when they've lost lock.  This comes up most often with
-altitude; because of the tall skinny shape of the tetrahedra defined
-by GPS range data, a GPS can lose 3D lock but still have an altitude
-guess good enough for it to deliver a 2D fix with confidence.  But
-just because GPSes fudge is no good reason for gpsd to add a layer of
-prevarication on top of that.</p>
-
-<p>But the conclusive argument against wiring in this policy is that,
-while it can be simulated by buffering data delivered according to a
-clear-every-cycle policy, the reverse is not true.  Under this policy
-there would be no way to distinguish in <code>gpsd</code>'s reports
-between data valid now and data held over from a previous cycle; on
-the other hand, under a clear-at-start-of-cycle policy the client can
-still do whatever buffering and smoothing it wants to.</p>
-
-<p>This is the policy gpsd currently follows when J=1 (not the default).</p>
-
-<h3 id="baroeptood">Buffer all, report on every packet, time out old data</h3>
-
-<p>gpsd does not presently keep the sort of per-field ageing data needed 
-to track the age of different TPV fields separately.  But it does know
-how many seconds have elapsed since the last packet receipt &mdash; it uses
-this to tell if the device has dropped offline, by looking for an age
-greater than the cycle time.</p>
-
-<p>When the device is returning fixes steadily, this policy will look
-exactly like "buffer all, report on every packet, never clear data",
-because every piece of data will be refreshed once per cycle.  It will
-have the same sort of prevarication problems as that policy, too.  If
-the device loses lock, the user will see that the TPV data is
-undefined only when the timeout expires.</p>
-
-<p>Fine-grained timeouts using per-field aging wouldn't change this 
-picture much.  They'd mainly be useful for matching the timeout 
-on a piece of data to its "natural" lifetime &mdash; usually 1 sec for
-TPV data and 5 sec for satellite-picture data.</p>
-
-<h2 id="noperfect">There is no perfect option</h2>
-
-<p>Any potential data-management policy would have drawbacks for some
-devices even if it were implemented perfectly.  The more complex
-policies would have an additional problem; buffering code with
-complicated flush triggers is notoriously prone to grow bugs near its
-edge cases.</p>
-
-<p>Thus, <code>gpsd</code> has a serious, gnarly data-management
-problem at its core.  This problem lurks behind many user bug reports
-and motivates some of the most difficult-to-understand code in the
-daemon.  And when you look hard at the problems posed by the variable
-sequences of sentences in NMEA devices...it gets even nastier.</p>
-
-<p>It's tempting to think that, if we knew the device type in advance,
-we could write a state machine adapted to its sentence sequence that
-would do a perfect job of data management.  The trouble with this
-theory is that we'd need separate state machines for each NMEA
-dialect.  That way lies madness &mdash; and an inability to cope
-gracefully with devices never seen before.  Since the
-zero-configuration design goal means that we can't count on the user
-or administrator passing device-type information to <code>gpsd</code>
-in the first place, we avoid this trap.</p>
-
-<p>But that means <code>gpsd</code> has to adapt to what it sees
-coming down the wire.  At least it can use a different policy for each
-device driver, dispatching once the device type has been
-identified.</p>
-
-<h2 id="interpolation">Combining buffering with interpolation: a speculative design</h2>
-
-<p>One possible choice (not let implemented in <code>gpsd</code> or
-its client libraries) would be to combine buffering with
-interpolation.  Here's a speculative design for a client which does
-its own extrapolation:</p>
-
-<p>Thread 1: GPS handler.  Sets watcher mode.  Each time a report is
-received, it stores that data along with the result of a call to
-gettimeofday() (so that we have microsecond precision, rather than
-just seconds from time()).  No need to double-buffer any data - just the
-latest complete O report is sufficient.  When the client receives a query
-from thread 2, it applies a differential correction to the last
-reported position, based on the last reported velocity and the
-difference between the stored gettimeofday() time and a new
-gettimeofday() call.</p>
-
-Thread 2: main application.  Driven by whatever events you want it
-to be.  Queries thread 1 whenever it needs an accurate GPS position
-NOW.
-
-<p>The main problem with this approach is that it would require an 
-onboard clock far more accurate than the GPS's once-per-second 
-reports.  This is a problem; in general, we can't assume that 
-a gpsd instance running in a car or boat will have access to
-<code>ntpd</code> or NIST radio time signals.</p>
-
 <h1 id="designahead">GPSD-NG, the Next-Generation GPSD Protocol</h1>
 
 <p>There are almost no more letters left in the namespace of the GPSD