docs/filter.adoc

   1 = Clock Filter Algorithm
   2 include::include-html.ad[]
   3
   4 The clock filter algorithm processes the offset and delay samples
   5 produced by the on-wire protocol for each peer process separately. It
   6 uses a sliding window of eight samples and picks out the sample with the
   7 least expected error. This page describes the algorithm design
   8 principles along with an example of typical performance.
   9
  10 image::pic/flt5.gif["Wedge Scattergram",align="center"]
  11
  12 Figure 1. Wedge Scattergram
  13
  14 Figure 1 shows a typical _wedge scattergram_ plotting sample points of
  15 offset versus delay collected over a 24 h period. As the delay
  16 increases, the offset variation increases, so the best samples are those
  17 at the lowest delay. There are two limb lines at slope ±0.5,
  18 representing the limits of sample variation. However, it is apparent
  19 that, if a way could be found to determine the sample of lowest delay, it
  20 would have the least offset variation and would be the best candidate to
  21 synchronize the system clock.
  22
  23 The clock filter algorithm works best when the delays are statistically
  24 identical in the reciprocal directions between the server and client.
  25 This is apparent in Figure 1, where the scattergram is symmetric about
  26 the x axis through the apex sample. In configurations where the delays
  27 are not reciprocal, or where the transmission delays on the two
  28 directions are traffic dependent, this may not be the case. A common
  29 case with DSL links is when downloading or uploading a large file.
  30 During the download or upload process, the delays may be significantly
  31 different resulting in large errors. However, these errors can be
  32 largely eliminated using samples near the limb lines, as described on
  33 the link:huffpuff.html[Huff-n'-Puff Filter] page.
  34
  35 In the clock filter algorithm the offset and delay samples from the
  36 on-wire protocol are inserted as the youngest stage of an eight-stage
  37 shift register, thus discarding the oldest stage. Each time an NTP
  38 packet is received from a source, a dispersion sample is initialized as
  39 the sum of the precisions of the server and client. Precision is defined
  40 by the latency to read the system clock and varies from 1000 ns to 100
  41 ns in modern machines. The dispersion sample is inserted in the shift
  42 register along with the associated offset and delay samples.
  43 Subsequently, the dispersion sample in each stage is increased at a
  44 fixed rate of 15 μs/s, representing the worst case error due to skew
  45 between the server and client clock frequencies.
  46
  47 In each peer process the clock filter algorithm selects the stage with
  48 the smallest delay, which generally represents the most accurate data,
  49 and it and the associated offset sample become the peer variables of the
  50 same name. The peer jitter statistic is computed as the root mean square
  51 (RMS) differences between the offset samples and the offset of the
  52 selected stage.
  53
  54 The peer dispersion statistic is determined as a weighted sum of the
  55 dispersion samples in the shift register. Initially, the dispersion of
  56 all shift register stages is set to a large number "infinity" equal to
  57 16 s. The weight factor for each stage, starting from the youngest
  58 numbered _i_ = 1, is 2^-_i_^, which means the peer dispersion is
  59 approximately 16 s.
  60
  61 As samples enter the register, the peer dispersion drops from 16 s to 8
  62 s, 4 s, 2 s, and so forth. In practice, the synchronization distance,
  63 which is equal to one-half the delay plus the dispersion, falls below
  64 the select threshold of 1.5 s in about four updates. This gives some
  65 time for meaningful comparison between sources, if more than one are
  66 available. The dispersion continues to grow at the same rate as the
  67 sample dispersion. For additional information on statistical principles
  68 and performance metrics, see the link:stats.html[Performance Metrics]
  69 page.
  70
  71 As explained elsewhere, when a source becomes unreachable, the poll
  72 process inserts a dummy infinity sample in the shift register for each
  73 poll sent. After eight polls, the register returns to its original
  74 state.
  75
  76 image:pic/flt1.gif["Raw",align="left"] image:pic/flt2.gif["Filtered",align="right"]
  77
  78 Figure 2. Raw (left) and Filtered (right) Offsets
  79
  80 Figure 2 shows the performance of the algorithm for a typical Internet
  81 path over a 24 h period. The graph on the left shows the raw offsets
  82 produced by the on-wired protocol, while the figure on the right shows
  83 the filtered offsets produced by the clock filter algorithm. If we
  84 consider the series formed as the absolute value of the offset samples,
  85 the mean error is defined as the mean of this series. Thus, the mean
  86 error of the raw samples is 0.724 ms, while the mean error of the
  87 filtered series is 0.192 ms. Radio engineers would interpret this as a
  88 processing gain of 11.5 dB.
  89
  90 The reader might notice the somewhat boxy characteristic of the filtered
  91 offsets. Once a sample is selected, it remains selected until a newer
  92 sample with lower delay is available. This commonly occurs when an older
  93 selected sample is discarded from the shift register. The reason for
  94 this is to preserve causality; that is, time always moves forward, never
  95 backward. The result can be the loss of up to seven samples in the shift
  96 register, or -- more to the point -- the output sample rate can never be less
  97 than one in eight input samples. The clock discipline algorithm is
  98 specifically designed to operate at this rate.
  99
 100 '''''
 101
 102 include::includes/footer.adoc[]