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.
Computer Network Time
Synchronization
Time Synchronization Basics
Computer clocks can drift
and must be periodically
synchronized over a
network
TheEhappens-before
relationEstates that events
on one computer happen
before news of those events
reaches another computer
Lamport's algorithm:
Servers send their
current time in
messages
Clients advance their
clock if a received
time is later than their
clock
Clocks are never set
backwards to avoid
violating happens-
before
Network time
protocolsElike NTP and
DTSS synchronize clocks
accounting for network
delays
NTP goal is to synchronize
clocks to within a few
milliseconds
ofECoordinated Universal
Time (UTC)
Time Synchronization
Protocols
Protocols estimate client's
time offset versus server
clocks
Offset is estimated by client
sending a request and
measuring round-trip delay
Protocols operate
overEmultiple stratum
levelsE- servers at one level
synchronize clients at the
next level
Three association
modes:
Persistent: Always
on
Preemptable:
Demobilize if no
response after
timeout
Ephemeral: Create
on-demand,
demobilize after
timeout
Common modes:
Client/Server: Client
polls stateless server
Symmetric: Peers
sync each other
Broadcast: Single
server syncs many
clients
Configuration
managementEis needed to
find servers and balance
load
Computer Clocks
Clocks based on quartz
oscillators that tick at
millisecond intervals
Clock error hasEsystematic
offsetEandErandom
jitterEcomponents
NTP estimates both time
offset and frequency offset
terms
Sync protocols adjust clock
to minimize offset
SmallEpoll intervals (<15
min)Eneeded for millisecond
accuracy
Processing Time Values
NTP usesEengineered
algorithmsElike cliques,
clustering, combining to
select good time values
Key NTP principle: Worst-
case error reading remote
clock is half the round-trip
delay
NTP acts as aEdigital
signal processorEusing
techniques like filtering and
feedback
Highlights
Synchronizing computer
clocks is critical for
distributed systems
Protocols like NTP and DTSS
synchronize clocks
accounting for network
delays
NTP uses advanced
algorithms to filter noise
and provide robust
synchronization
Typical goal is to
synchronize clocks to within
a few milliseconds of UTC
How NTP Works
NTP Daemon Architecture
NTP daemon implements
peer and poll processes for
each server
Peer process handles time
request replies and
calculates time offset and
delay
Poll process periodically
sends time requests based
on network conditions
Offset and delay values are
saved per association and
groomed by clock filter
Timestamp Representation
NTP uses 64-bit short
format and 128-bit long
format timestamps
Short format has 32 bits for
whole seconds since 1900
and 32 bits for fraction of
second
Long format has 64 bits for
seconds and 64 bits for
fraction - extremely high
precision
Short format mapped from
bits 32-63 of long format.
Can represent unambiguous
years 1900-2036
Long format can represent
dates from the dawn of the
universe to the far future
Computations use
differences between
timestamps to preserve
precision
Reckoning Time
Basic NTP time reckoning:
Client A sends its time
T1 to server B
B replies with its
times T2, T3 and
client's original T1
A computes offset θ
and delay δ relative to
B
Offset and delay values
filtered and processed by:
Selection algorithm -
discards falsetickers
Clustering algorithm -
selects most accurate
candidates
Combining algorithm -
averages offsets of
survivors
Result is best offset
estimate relative to server
population
Clock Discipline
NTP adjusts system clock
time and frequency to
minimize offset
Hardware clock ticks
regularly to advance
software clock
But clocks have intrinsic
frequency errors and
temperature dependence
NTP discipline algorithm
corrects for these errors
about once per second
Can reduce errors to
microseconds with kernel
timekeeping support
Association Modes
Client/server: Client polls
stateless server
Symmetric: Peers sync each
other
Broadcast: Server pushes
time to many clients
Each NTP host can operate
in any combination of
modes
Modes determine time flow
direction and configuration
Highlights
NTP calculates offset/delay
relative to servers with
timestamp exchanges
Short and long timestamp
formats represent time to
high precision
Engineered algorithms filter
noise to produce best offset
estimate
Clock discipline
compensates for intrinsic
clock errors
Major modes define time
flow and configuration
methods
NTP in the Internet
NTP Protocol Versions
NTPv3 is the official
standard specified in RFC
1305
NTPv4 extends NTPv3 but
has no single defining
specification yet
SNTPv4 is a compatible
subset for simple clients
and servers
Importance of Common
Algorithms
Early NTP specs separated
architecture from
implementation
But Internet NTP servers are
now a tightly coupled
system
So common algorithms are
needed for stability,
especially for clock
discipline
NTPv4 reference
implementation contains
carefully engineered
algorithms
These algorithms likely
need to be standardized
going forward
Widespread Adoption
NTPv4 reference
implementation is a product
of many years of volunteer
work
Compatible with but
extends previous versions
NTP is likely the longest
continuously running
Internet application protocol
Widely deployed on hosts
and routers across the
Internet
Used for research, services,
air traffic control, stock
trading, and many
corporate networks
Public NTP servers operated
by national standards labs
worldwide
Availability
NTPv4 reference
implementation and docs
available for free at ntp.org
Ported to many
architectures from PCs to
supercomputers
Build process is automated
and requires minimal
system configuration
Online resources include
technical articles, news, and
discussion forums
Highlights
NTPv3 is the official
standard but NTPv4 widely
used in practice
NTP algorithms are crucial
for stability in the Internet
Widespread adoption for
critical functions like finance
and air traffic control
NTPv4 reference
implementation available
and runs on most
architectures
Global infrastructure of
public servers plus many
private deployments
