docs/cluster.adoc

   1 = Clock Cluster Algorithm
   2 include::include-html.ad[]
   3
   4 The clock cluster algorithm processes the truechimers produced by the
   5 clock select algorithm to produce a list of _survivors_. These survivors
   6 are used by the mitigation algorithms to discipline the system clock.
   7 The cluster algorithm operates in a series of rounds, where at each
   8 round the truechimer furthest from the offset centroid is pruned from
   9 the population. The rounds are continued until a specified termination
  10 condition is met. This page discusses the algorithm in detail.
  11
  12 First, the truechimer associations are saved on an unordered list with
  13 each candidate entry identified with index __i__ (__i__ = 1, ..., __n)__,
  14 where __n__ is the number of candidates. Let θ(__i__), be the offset and
  15 λ(__i__) be the root distance of the __i__th entry. Recall that the root
  16 distance is equal to the root dispersion plus half the root delay. For
  17 the __i__th candidate on the list, a statistic called the _select jitter_
  18 relative to the __i__th candidate is calculated as follows. Let
  19
  20 __d~i~__(__j__) = |θ(__j__) − θ(__i__)| λ(__i__),
  21
  22 where θ(__i)__ is the peer offset of the __i__th entry and θ(__j__) is the
  23 peer offset of the __j__th entry, both produced by the clock filter
  24 algorithm. The metric used by the cluster algorithm is the select jitter
  25 φ~S~(__i__) computed as the root mean square (RMS) of the __d~i~__(__j__) as
  26 __j__ ranges from 1 to __n__. For the purpose of notation in the example
  27 to follow, let φ~R~(__i__) be the peer jitter computed by the clock filter
  28 algorithm for the __i__th candidate.
  29
  30 The object at each round is to prune the entry with the largest metric
  31 until the termination condition is met. Note that the select jitter must
  32 be recomputed at each round, but the peer jitter does not change. At
  33 each round the remaining entries on the list represent the survivors of
  34 that round. If the candidate to be pruned is preemptable and the number
  35 of candidates is greater than the _maxclock_ _threshold_, the association
  36 is demobilized. This is useful in the schemes described on the
  37 link:discover.html[Automatic Server Discovery Schemes] page. The
  38 maxclock threshold default is 10, but it can be changed using the
  39 +maxclock+ option of the link:miscopt.html#tos[+tos+] command. Further
  40 pruning is subject to the following termination conditions, but no
  41 associations will be automatically demobilized.
  42
  43 The termination condition has two parts. First, if the number of
  44 survivors is not greater than the _minclock_ _threshold_ set by the
  45 +minclock+ option of the link:miscopt.html#tos[+tos+] command, the
  46 pruning process terminates. The _minclock_ default is 3, but can be
  47 changed to fit special conditions, as described on the
  48 link:prefer.html[Mitigation Rules and the prefer Keyword] page.
  49
  50 image:pic/flt7.gif[]
  51
  52 Figure 1. Cluster Algorithm
  53
  54 The second termination condition is more intricate. Figure 1 shows a
  55 round where a candidate of (a) is pruned to yield the candidates of (b).
  56 Let φ~max~ be the maximum select jitter and φ~min~ be the minimum
  57 peer jitter over all candidates on the list. In (a), candidate 1 has the
  58 highest select jitter, so φ~_max_~ = φ~S~(1). Candidate 4 has the lowest
  59 peer jitter, so φ~min~ = φ~R~(4). Since φ~max~ > φ~min~, select
  60 jitter dominates peer jitter, the algorithm prunes candidate 1. In (b),
  61 φ~max~ = φ~S~(3) and φ~min~ =φ~R~(4). Since φ~max~ < φ~min~,
  62 pruning additional candidates does not reduce select jitter, the
  63 algorithm terminates with candidates 2, 3 and 4 as survivors.
  64
  65 The survivor list is passed on to the mitigation algorithms, which
  66 combine the survivors, select a system peer, and compute the system
  67 statistics passed on to dependent clients. Note the use of root distance
  68 λ as a weight factor at each round in the clock cluster algorithm. This
  69 is to favor the survivors with the lowest root distance and thus the
  70 smallest maximum error.
  71
  72 '''''
  73
  74 include::includes/footer.adoc[]