Clock Filter Algorithm

Clock Filter Algorithm The NTP clock filter algorithm selects the best time offset samples while rejecting noise spikes caused by packet collisions and network congestion.    NTP calculates clock offset θ and round-trip delay δ from four timestamp exchanges Goal is to estimate the true offset θ and delay δ when the path is idle Observations:    Packet networks often operate below capacity, with low queue occupancy Routing minimizes hops, so both directions are unlikely to see congestion Therefore, lowest delay samples likely represent true offset Algorithm The clock filter algorithm maintains a shift register of the last n samples: (θ1, δ1, ε1, t1) ... (θn, δn, εn, tn)  θ, δ are the measured offset and delay  ε grows at 15 ppm to represent sample error  t is the sample time On new sample (θ0, δ0, ε0, t0): 1. Shift new sample into register, discard oldest 2. Sort samples by quality metric λ prioritizing lowest delay: λj = δj + max(εj - σy(tj), 0) 3. Update peer offset θ and delay δ with best sample 4. Calculate peer dispersion ε as RMS of samples 5. Trim poor samples from sorted list 6. Compute peer jitter φ from surviving samples This minimum filter produces the best offset estimates during congestion. Selection Algorithm The selection algorithm identifies truechimers among a set of time servers.  NTP uses multiple redundant servers over diverse network paths  Must identify truechimers and discard falsetickers For each server i:  θi is measured offset  Δi is root delay  Ei is root dispersion Root distance Λi = Δi + Ei/2 This defines the confidence interval [θi - Λi, θi + Λi] that must contain the true offset. The algorithm finds the intersection interval containing ≥ m - f server midpoints. 1. Construct offset tuples (θi - Λi, 1), (θi, 0), (θi + Λi, +1) 2. Sort tuples by offset 3. Scan from lowest endpoint to find lower limit l 4. Scan from highest endpoint to find upper limit u 5. Repeat with increased f if needed to find interval with ≥ m - f midpoints The resulting intersection interval is guaranteed to contain the true offset.