The NTP clock filter algorithm is designed to select the best sample data while rejecting noise spikes due to packet collisions and network congestion. Recall that the clock offset 8 and round-trip delay 5 samples are computed from the four most recent timestamps. Without making any assumptions about the delay distributions but assuming the frequency difference or skew between the server and peer clocks can be neglected, let (8, 5) represent the offset and delay when the path is otherwise idle and thus the true values. The problem is to produce an accurate estimator (0, 8) from a sample sequence
collected for the path over an appropriate interval under ambient traffic conditions.
The design of the clock filter algorithm was suggested by the observation that packet-switching networks are most often operated well below the knee of the throughput-delay curve. This means that packet queues are mostly small with relatively infrequent packet bursts. In addition, the routing algorithm most often operates to minimize the number of packet-switch hops and thus the number of queues. Not only is the probability that an NTP packet finds a busy queue in one direction relatively low, but the probability of packets from a single exchange finding busy queues in both directions is even lower. Therefore, the best offset samples should occur with the lowest delays.
The characteristics of a typical Internet path are illustrated in Figure 3.3, called a wedge scattergram. Scattergrams like these plot samples
over intervals of hours to months. Network delays in this and other plots in this topic were constructed using the NTP simulator, which includes all the algorithms of the reference implementation, driven by zero-mean exponential distributions with specified standard deviation
The particular path models seven networks and 12 routers and was among the most complex in the Internet of 1986. The choice
ms was made by inspection from old tattered performance plots unsuitable for reproduction here.
Under low-traffic conditions, the points are concentrated about the apex of the wedge and begin to extend rightward along the limb lines as network traffic increases.
FIGURE 3.3
Wedge scattergram.
As the traffic continues to increase, the points begin to fill in the wedge as it expands even further right-ward. From these data, it is obvious that good estimators
are points near the apex, which is exactly what the clock filter algorithm is designed to produce.
This observation suggests the design of what is called here a minimum filter consisting of a shift register holding samples
On arrival of a packet, a new entry
shifts into the register, and the oldest one is discarded. Here,
are from Equation 3.2, and
is the epoch at T4.If a packet has not arrived for four successive poll intervals, a dummy sample 
is shifted into the register, where
represents missing data.
While missing data samples are never used in subsequent calculations, they shove very old samples out of the register to prevent them from being used.
Next, the register contents are copied to a temporary list and sorted by the metric X designed to avoid missing data and devalue samples older than the Allan intercept:
The intended algorithm is an exchange sort; however, an exchange is not made unless to do so would reduce the metric by at least the value of the precision. In other words, it does not make sense to change the order in the list, which might result in the loss of otherwise good samples, unless the metric change is significant.
The first entry
on the temporary list represents the lowest delay sample that is used to update the peer offset
and peer delay
The peer dispersion e is calculated from the temporary list:
Finally, the temporary list is trimmed by discarding all entries
and all but the first devalued entry, if one is present, leaving
surviving entries on the list. The peer jitter 9 is used by the cluster algorithm as a quality metric and in the computation of the expected error
A popcorn spike is a transient outlier, usually only a single sample, that is typical of congested Internet paths. The popcorn spike suppressor is designed to detect and remove them. Let
be the peer offset determined by the previous message and 9 the current peer jitter. If
where
is a tuning parameter that defaults to 3, the sample is a popcorn spike and is discarded. Note that the peer jitter will increase to protect a legitimate step change.
As demonstrated by simulation and practical experience, it is prudent to avoid using samples older than the latest one used. Let
be the epoch that the peer variables were last updated and
be the epoch of the first sample on the temporary list. If
the new sample is a duplicate or earlier than the last one used. If this is true, the algorithm exits without updating the system clock; otherwise,
and the offset can be used. Note that this can result
in the discard of all but one sample in the clock filter, but there will always be one sample. The components of the tuple
are called the peer variables elsewhere in this topic. Note that if a burst option is enabled, the system clock is not updated until the last packet in the burst.
Several experiments were made to evaluate this design using measurements between NTP primary servers so that delays and offsets could be determined independently of the measurement procedure itself [22]. The experiments were performed over several paths involving ARPANET, NSFNET (National Science Foundation Network), and various LANs and using minimum filters and various other algorithms based on median and trimmed-mean statistics. The results showed consistently lower errors for the clock filter algorithm when compared with the other algorithms. Perhaps the most dramatic result with the clock filter algorithm was the greatly reduced maximum error with moderate-to-severe network congestion.
For example, Figure 3.4 shows the offsets simulated for a typical Internet path over a 24-h period with a 64-s poll interval. In this case, the network delays were modeled as a zero-mean exponential distribution with
ms. Figure 3.5 shows a cumulative distribution function (CDF) for the raw offsets (right curve) and filtered offsets (left curve). The result is a decrease in maximum error from 37 to 7.6 ms and a decrease in standard deviation from 7.1 to 1.95 ms.
