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.
|
|