Previous  Top  Next

Windows Time Server

4.1 Clock-Filter Procedure

The clock-filter procedure is executed upon arrival of an NTP message or other event that results in new data samples. It takes arguments of the form theta, delta, epsilon, where theta is a sample clock offset measurement and delta and epsilon are the associated roundtrip delay and dispersion. It determines the filtered clock offset (peer.offset), roundtrip delay (peer.delay) and dispersion (peer.dispersion). It also updates the dispersion of samples already recorded and saves the current time (peer.update).

The basis of the clock-filter procedure is the filter shift register (peer.filter), which consists of NTP.SHIFT stages, each stage containing a 3-tuple [ theta sub i , delta sub i , epsilon sub i ], with indices numbered from zero on the left. The filter is initialized with the value [0,0, NTP.MAXDISPERSE] in all stages by the clear procedure. New data samples are shifted into the filter at the left end, causing first NULLs then old samples to fall off the right end. The packet procedure provides samples of the form [theta, delta, epsilon] as new updates arrive, while the transmit procedure provides samples of the form [0,0, NTP.MAXDISPERSE] when two poll intervals elapse without a fresh update. While the same symbols (theta ,delta ,epsilon) are used here for the arguments, clock-filter contents and peer variables, the meaning will be clear from context. The following pseudo-code describes this procedure.

begin clock-filter procedure (theta ,delta ,epsilon)

The dispersion epsilon sub i for all valid samples in the filter register must be updated to account for the skew-error accumulation since the last update. These samples are also inserted on a temporary list with entry format [distance,index]. The samples in the register are shifted right one stage, with the overflow sample discarded and the new sample inserted at the leftmost stage. The temporary list is then sorted by increasing distance. If no samples remain in the list, the procedure exits without updating the peer variables.

       for (i from NTP.SIZE - 1 to 1) begin        /* update dispersion */
               [ theta sub i ,delta sub i ,epsilon sub i ] <-- [theta sub {i-1} ,delta sub {i-1} ,epsilon sub {i-1} ];             
                                                               /* shift stage right */
               epsilon sub i = epsilon sub i + phi tau;
               add  [ lambda sub i == epsilon sub i + {| delta  sub i |} over 2 , i]  to temporary list;
               endfor;
       [ theta sub 0 ,delta sub 0 ,epsilon sub 0 ] <-- [ theta ,delta ,epsilon ];        /* insert new sample */
       add [ lambda == epsilon + {| delta |} over 2 ,0] to temporary list;
       peer.update <-- sys.clock;                      /* reset base time */
       sort temporary list by increasing [distance ||index];

where [distance ||index] represents the concatenation of the distance and index fields and distance is the high-order field. The filter dispersion epsilon sub sigma is computed and included in the peer dispersion. Note that for this purpose the temporary list is already sorted.

       epsilon sub sigma <-- 0;
       for (i from NTP.SHIFT - 1 to 0)               /* compute filter dispersion */
               if (peer.dispersion sub index[i] >= NTP.MAXDISPERSE or
                       | theta sub i - theta sub 0 | > NTP.MAXDISPERSE
                       epsilon sub sigma <-- epsilon sub sigma + NTP.MAXDISPERSE) times NTP.FILTER;
               else
                       epsilon sub sigma <-- ( epsilon sub sigma + | theta sub i - theta sub 0 |) times NTP.FILTER;

The peer offset theta sub 0, delay delta sub 0 and dispersion epsilon sub 0 are chosen as the values corresponding to the minimum-distance sample; in other words, the sample corresponding to the first entry on the temporary list, here represented as the 0th subscript.

       peer.offset <-- theta sub 0;                    /* update peer variables */
       peer.delay <-- delta sub 0;
       peer.dispersion <-- min ( epsilon sub 0 + epsilon sub sigma , NTP.MAXDISPERSE);
end clock-filter procedure

The peer.offset and peer.delay variables represent the clock offset and roundtrip delay of the local clock relative to the peer clock. Both of these are precision quantities and can usually be averaged over long intervals in order to improve accuracy and stability without bias accumulation (see Appendix H). The peer.dispersion variable represents
the maximum error due to measurement error, skew-error accumulation and sample variance. All three variables are used in the clock-selection and clock-combining procedures to select the peer clock(s) used for synchronization and to maximize the accuracy and stability of the indications.