Windows Time Server


4.2.1 Intersection Algorithm

Previous  Top  Next

 

begin clock-selection procedure

 

Each peer is examined in turn and added to an endpoint list only if it passes several sanity checks designed to avoid loops and use of exceptionally noisy data. If no peers survive the sanity checks, the procedure exits without finding a synchronization source. For each of m survivors three entries of the form [endpoint,type] are added to the endpoint list: [ THETA- LAMBDA ,-1], [ THETA ,0] and [ THETA + LAMBDA ,1]. There will be 3 m entries on the list, which is then sorted by increasing endpoint.

 

       m <-- 0;

       for (each peer)                         /* calling all peers */

               if (peer.reach != 0 and peer.dispersion < NTP.MAXDISPERSE and

                       not (peer.stratum > 1 and peer.refid = peer.hostaddr)) begin

                       LAMBDA andistance (peer);                 /* make list entry */

                       add  [THETA - LAMBDA ,-1] to endpoint list;

                       add  [THETA ,0]  to endpoint list;

                       add  [THETA + LAMBDA ,1]> to endpoint list;

                       m <--  m+1;

                       endif

               endfor

       if (m = 0) begin                            /* skedaddle if no candidates */

               sys.peer <-- NULL;

               sys.stratum <-- 0 (undefined);

               exit;

               endif

       sort endpoint list by increasing endpoint||type;

 

The following algorithm is adapted from DTS [DEC89] and is designed to produce the largest single intersection containing only truechimers. The algorithm begins by initializing a value f and counters i and c to zero. Then, starting from the lowest endpoint of the sorted endpoint list, for each entry [endpoint,type] the value of type is subtracted from the counter i, which is the number of intersections. If type is zero, increment the value of c, which is the number of falsetickers (see Appendix H). If i >= m- f  for some entry, endpoint of that entry becomes the lower endpoint of the intersection; otherwise, f is increased by one and the above procedure is repeated. Without resetting f or c, a similar procedure is used to find the upper endpoint, except that the value of type is added to the counter.. If after both endpoints have been determined c <=f , the procedure continues having found m - f truechimers; otherwise, f is increased by one and the entire procedure is repeated.

 

       for (f from 0 to f >= m over 2) begin              /* calling all truechimers */

               c <-- 0;

               i  <-- 0;

               for (each [endpoint, type] from lowest) begin   /* find low endpoint */

                       i <-- i - type;

                       low <-- endpoint;

                       if (i >= m - f) break;

                       if (type = 0)  c <-- c + 1 ;

                       endfor;

               i <-- 0;

 

               for (each [endpoint, type] from highest) begin  /* find high endpoint */

                       i <-- i + type;

                       high <-- endpoint;

                       if ( i >= m - f ) break;

                       if ( type = 0) c <-- c + 1;

                       endfor;

               if ( c <= f) break;                 /* continue until all falsetickers found */

               endfor;

       if ( low > high) begin                              /* quit if no intersection found */

               sys.peer <- NULL;

               exit;

               endif;

 

Note that processing continues past this point only if there are more than m over 2 intersections. However, it is possible, but not highly likely, that there may be fewer than  m over 2 truechimers remaining in the intersection.

 

 


Bytefusion Software Prices Site Map Purchase This Product On-line
How to Order Windows Time Products Time Client for Windows
Windows Time Server USB GPS
Products
Download
Order
Support
GPS Sales
Contact
News
Home