Previous  Top  Next

Windows Time Client

4.2.2. Clustering Algorithm

In the original DTS algorithm the clock-selection procedure exits at this point with the presumed correct time set midway in the computed intersection [low,high]. However, this can lead to a considerable loss in accuracy and stability, since the individual peer statistics are lost. Therefore, in NTP the candidates that survived the preceding steps are processed further. The candidate list is rebuilt with entries of the form [distance,index], where distance is computed from the (scaled) peer stratum and synchronization distance LAMBDA. The scaling factor provides a mechanism to weight the combination of stratum and distance. Ordinarily, the stratum will dominate, unless one or more of the survivors has an exceptionally high distance. The list is then sorted by increasing distance.

       m <-- 0;
       for (each peer) begin                   /* calling all peers */
               if (low  <= theta <= high) begin
                       LAMBDA <-- distance (peer);    /* make list entry */
                       ist <-- peer.stratum * NTP.MAXDISPERSE + LAMBDA >
                       add [ dist ,peer]  to candidate list;
                       m <-- m + 1;
                       endif;
               endfor;
       sort candidate list by increasing dist;

The next steps are designed to cast out outlyers which exhibit significant dispersions relative to the other members of the candidate list while minimizing wander, especially on high-speed LANs with many time servers. Wander causes needless network overhead, since the poll interval is clamped at sys.poll as each new peer is selected for synchronization and only slowly increases when the peer is no longer selected. It has been the practical experience that the number of candidates surviving to this point can become quite large and can result in significant processor cycles without materially

enhancing stability and accuracy. Accordingly, the candidate list is truncated at NTP.MAXCLOCK entries.

Note epsilon sub {xi i} is the select (sample) dispersion relative to the ith peer represented on the candidate list, which can be calculated in a manner similar to the filter dispersion described previously. The EPSILON sub j  is the dispersion of the jth peer represented on the list and includes components due to measurement error, skew-error accumulation and filter dispersion. If the maximum epsilon sub {xi i} is greater than the minimum EPSILON sub j and the number of survivors is greater than NTP.MINCLOCK, the ith peer is discarded from the list and the procedure is repeated. If the current synchronization source is one of the survivors and there is no other survivor of lower stratum, then the procedure exits without doing anything further. Otherwise, the synchronization source is set to the first survivor on the candidate list. In the following i, j, k, l are peer indices, with k the index of the current synchronization source (NULL if none) and l the index of the first survivor on the candidate list.

       while begin
               for (each survivor [distance,index]) begin        /* compute dispersions */
                       find index i for max epsilon sub {xi i};
                       find index j for min EPSILON sub j;
                       endfor
               if (epsilon sub {xi i} <= EPSILON sub j or m <= NTP.MINCLOCK) break;
               peer.survivor [i] <-- 0;             /* discard ith peer */
               if (i = k ) sys.peer <-- NULL;
               delete the ith peer from the candidate list;
               m <-- m - 1;
               endwhile
       if (peer.survivor [k] = 0 or peer.stratum[k] > peer.stratum [l]>) begin
               sys.peer <-- l;                               /* new clock source */

               call poll-update;
               endif
end clock-select procedure;


The algorithm is designed to favor those peers near the head of the candidate list, which are at the lowest stratum and distance and presumably can provide the most accurate and stable time. With proper selection of weight factor v (also called NTP.SELECT), entries will be trimmed from the tail of the list, unless a few outlyers disagree significantly with respect to the remaining entries, in which case the outlyers are discarded first. The termination condition is designed to avoid needless switching between synchronization sources when not statistically justified, yet maintain a bias toward the low-stratum, low-distance peers.