1*2b15cb3dSCy Schubert<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 2*2b15cb3dSCy Schubert<html> 3*2b15cb3dSCy Schubert<head> 4*2b15cb3dSCy Schubert<meta http-equiv="content-type" content="text/html;charset=iso-8859-1"> 5*2b15cb3dSCy Schubert<meta name="generator" content="HTML Tidy, see www.w3.org"> 6*2b15cb3dSCy Schubert<title>Clock Cluster Algorithm</title> 7*2b15cb3dSCy Schubert<link href="scripts/style.css" type="text/css" rel="stylesheet"> 8*2b15cb3dSCy Schubert</head> 9*2b15cb3dSCy Schubert<body> 10*2b15cb3dSCy Schubert<em></em> 11*2b15cb3dSCy Schubert<h3>Clock Cluster Algorithm</h3> 12*2b15cb3dSCy Schubert<p>Last update: 13*2b15cb3dSCy Schubert <!-- #BeginDate format:En2m -->15-Nov-2012 06:02<!-- #EndDate --> 14*2b15cb3dSCy Schubert UTC</p> 15*2b15cb3dSCy Schubert<hr> 16*2b15cb3dSCy Schubert<p>The clock cluster algorithm processes the truechimers produced by the clock select algorithm to produce a list of <em>survivors</em>. These survivors are used by the mitigation algorithms to discipline the system clock. The cluster algorithm operates in a series of rounds, where at each round the truechimer furthest from the offset centroid is pruned from the population. The rounds are continued until a specified termination condition is met. This page discusses the algorithm in detail.</p> 17*2b15cb3dSCy Schubert<p>First, the truechimer associations are saved on an unordered list with each candidate entry identified with index <em>i</em> (<em>i </em>= 1, ..., <em>n)</em>, where <em>n</em> is the number of candidates. Let θ(<em>i</em>), be the offset and λ(<em>i</em>) be the root distance of the <em>i</em>th entry. Recall that the root distance is equal to the root dispersion plus half the root delay. For the <em>i</em>th candidate on the list, a statistic called the <em>select jitter</em> relative to the <em>i</em>th candidate is calculated as follows. Let</p> 18*2b15cb3dSCy Schubert<div align="center"> 19*2b15cb3dSCy Schubert <p><em>d<sub>i</sub></em>(<em>j</em>) = |θ(<em>j</em>) − θ(<em>i</em>)| λ(<em>i</em>),</p> 20*2b15cb3dSCy Schubert</div> 21*2b15cb3dSCy Schubert<p> where θ(<em>i)</em> is the peer offset of the <em>i</em>th entry and θ(<em>j</em>) is the peer offset of the <em>j</em>th entry, both produced by the clock filter algorithm. The metric used by the cluster algorithm is the select jitter φ<sub>S</sub>(<em>i</em>) computed as the root mean square (RMS) of the <em>d<sub>i</sub></em>(<em>j</em>) as <em>j</em> ranges from 1 to <em>n</em>. <em> </em>For the purpose of notation in the example to follow, let φ<sub>R</sub>(<em>i</em>) be the peer jitter computed by the clock filter algorithm for the <em>i</em>th candidate.</p> 22*2b15cb3dSCy Schubert<p>The object at each round is to prune the entry with the largest metric until the termination condition is met. Note that the select jitter must be recomputed at each round, but the peer jitter does not change. At each round the remaining entries on the list represent the survivors of that round. If the candidate to be pruned is preemptable and the number of candidates is greater than the <em>maxclock threshold</em>, the association is demobilized. This is useful in the schemes described on the <a href="discover.html">Automatic Server Discovery Schemes</a> page. The maxclock threshold default is 10, but it can be changed using the <tt>maxclock</tt> option of the <a href="miscopt.html#tos"><tt>tos</tt></a> command. Further pruning is subject to the following termination conditions, but no associations will be automatically demobilized.</p> 23*2b15cb3dSCy Schubert<p>The termination condition has two parts. First, if the number of survivors is not greater than the<em> </em><em>minclock threshold</em> set by the <tt>minclock</tt> option of the <a href="miscopt.html#tos"><tt>tos</tt></a> command, the pruning process terminates. The<tt> minclock</tt> default is 3, but can be changed to fit special conditions, as described on the <a href="prefer.html">Mitigation Rules and the prefer Keyword</a> page.</p> 24*2b15cb3dSCy Schubert<div align="center"><img src="pic/flt7.gif" alt="gif"> 25*2b15cb3dSCy Schubert <p>Figure 1. Cluster Algorithm</p> 26*2b15cb3dSCy Schubert</div> 27*2b15cb3dSCy Schubert<p>The second termination condition is more intricate. Figure 1 shows a round where a candidate of (a) is pruned to yield the candidates of (b). Let φ<sub><em>max</em></sub> be the maximum select jitter and φ<sub><em>min</em></sub> be the minimum peer jitter over all candidates on the list. In (a), candidate 1 has the highest select jitter, so φ<sub><em>max</em></sub> = φ<sub>S</sub>(1). Candidate 4 has the lowest peer jitter, so φ<sub><em>min</em></sub> = φ<sub>R</sub>(4). Since φ<sub><em>max</em></sub> > φ<sub><em>min</em></sub>, select jitter dominates peer jitter,the algorithm prunes candidate 1. In (b), φ<sub><em>max</em></sub> = φ<sub>S</sub>(3) and φ<sub><em>min </em></sub>=φ<sub>R</sub>(4). Since φ<sub><em>max</em></sub> < φ<sub><em>min</em></sub>, pruning additional candidates does not reduce select jitter, the algorithm terminates with candidates 2, 3 and 4 as survivors.</p> 28*2b15cb3dSCy Schubert<p>The survivor list is passed on to the the mitigation algorithms, which combine the survivors, select a system peer, and compute the system statistics passed on to dependent clients. Note the use of root distance λ as a weight factor at each round in the clock cluster algorithm. This is to favor the survivors with the lowest root distance and thus the smallest maximum error.</p> 29*2b15cb3dSCy Schubert<hr> 30*2b15cb3dSCy Schubert<script type="text/javascript" language="javascript" src="scripts/footer.txt"></script> 31*2b15cb3dSCy Schubert</body> 32*2b15cb3dSCy Schubert</html> 33
