> I have read several places to use many servers in my servers
> listings.. I presently have 12. Is there a practical limit where after
> ntp only gets sluggish and the extra servers don't really help it?
> I figured an 'even dozen' should be a good round number :)
12 is a bit on the generous side, but not totally unreasonable for a
critical server, and there's no problem whatsoever with even higher
numbers.
More is not always better. NTP resolves disputes between the servers
by looking for a majority consensus, so if you configure lots of lousy
servers, it's possible they can outvote your good servers. So don't be
a slut; maintain some standards.
The original NTP was designed to have all links configured, both
upstream and downstream. The current model where client requests are
(mostly) forgotten about as soon as they're replied to was added later.
Originally, you wouldn't have X servers and Y clients, you'd have X+Y
peers, and NTP would pick the best available time from that lot.
So it's designed to cope with a lot more "servers" than you expect.
However, there is O(n^2) processing inside NTP, so ridiculous numbers
will eventually slow it down.
Now, the number of peers/servers that NTP "uses" is hard to define.
There are several limits, and no limits, so let me explain.
First, I'll stop talking about "NTP" in general, and talk specifically
about the current ntpd implementation. These are implementation-specific
details, not inherent properties of the protocol.
There is no limit to the number of servers or peers that you can
configure. ntpd does enter them into a 128-entry hash table, but it's
open chained, so you can have more peers than there are hash table slots.
Anyway, ntpd exchanges time packets with each configured peer. Whenever
ntpd gets a new time value, it runs the clock select algorithm to pick
the best clock. This is where things get O(n^2). If you have 100 peers,
then you're going to get 100 responses every poll interval, and each time,
you're going to search a list of 100 clocks.
That's O(n^2), but keep it in perspective. The entire effort, which
will be spread out over a 1024-second poll interval, will be less work
for the CPU than uncompressing and displaying one JPG file.
Anyway, each peer produces a time correction and some associated error
estimates, and feeds it to the master NTP clock selection algorithm,
which tries to pick the best answer from multiple conflicting inputs.
This is were the magic starts.
"True genius resides in the capacity for evaluation of uncertain,
hazardous, and conflicting information."
-- Winston Churchill
These algorithms use multiple rounds of testing to narrow the field.
The round that a given peer survives until can be seen in the status
character displayed in the first column of the ntpq "peers" output.
There are seven possibilities (the eighth, "o" for the PPS peer, is a
special case I won't go into), indicating how many of the five rounds
of selection the peer has survived.
' ': Peer rejected for elementary reasons.
'x': Peer rejected as falseticker by intersection algorithm.
'.': Peer discarded as excess to the needs of clustering.
'#': Peer discardrd by clustering as too distant.
'-': Peer discarded by clustering as an outlyer.
'+': Peer is selected as a time source.
'*': System peer. This is the "best" of the selected
peers. I may have multiple teachers, but this one
is my thesis advisor.
Round 1: (failures marked by ' ')
Here, we discard peers based on per-peer information. Peers that don't
respond, peers that don't have time, peers that are synchronized to us,
peers that give us various out-of-bounds values.
Most of this is based on data supplied by the peer. If it
lies to us, it's pretty easy to get past this stage. See
ntpd/ntp_proto.c:peer_unfit()
Round 2: Intersection (failures marked by 'x')
Each peer sends us a "root distance", which is the worst-case error that
could possibly accumulate between true UTC and it. There are allowances
for the error reading the reference clock, the round-trip time to exchange
time packets, and clock drift on the servers between sending packets.
For every peer, I compute a root distance through it by taking its claimed
root distance, and adding half of the the round-trip time to talk to it,
plus an allowance for how much my clock could have drifted since I last
heard from it.
Anyway, if two peers are both sane, then the difference between their two
time claims should differ by at most the sum of their root distances.
If not, then at least one of them MUST be lying. The intersection
algorithm looks for an interval which more than half of the configured
peers agree must include correct UTC time. Peers outside that range
are discarded.
This is a basic pass/fail sanity test.
Generally, a correctly operating NTP peer CANNOT be declared a
falseticker and fail this test. Actually, ntpd is a bit pickier:
a correctly operating peer must give a time interval (claimed time,
plus/minus root distance) that OVERLAPS the intersection region, but
ntpd discards peers whose claimed time is not IN the interval.
That is, if NTP decides that true time correction must be between -10 and
+30 ms, and a peer claims "-20 ms, +/-50 ms", then it's not technically
wrong, but it will be excluded anyway.
Round 3: Take the best NTP_MAXCLOCK (failures marked by '.')
Peers that survive the intersection are all pretty good, so if there are
a lot, NTP takes only those with the lowest strata and root distances.
In older ntpd 4.0.x versions, NTP_MAXCLOCK was 10, so you'd see the
'.' occasionally. In newer 4.2.x versions, the corresponding value is
NTP_MAXASSOC, and it's 50, so you'll probably never see this test fail.
(Also, in 4.2.5, excluded clocks are marked with '#', and '.' is never
used. Clustering failures are marked with '-' only.)
Round 4: Statistical clustering (failures marked by '#' and '-')
This is an iterative test, where the times are averaged, and the "worst"
peer is excluded. The defintiion of "worst" is a complex heuristic I
won't go into here, but it includes how far the peer's reported time
differs from the overall average, and the estimated error.
This continues until:
- The peers agree among each other as well as the best of them agrees
with itself. This compares the "peer jitter" (how much different
time corrections from one peer vary) with the "select jitter" (how
much the time corrections from the various peers agree with each other).
- We have reduced the list to ntp_minpeer=3.
- The worst remaining peer is a "prefer" peer.
Dropouts are marked with '#' if they are too far from a root time server,
and '-' if they are excluded as outlyers.
Round 5: Choose the system peer from the survivors
Nobody really "fails" here, but the system peer is marked '*' and the
others used to compute a clock average are marked '+'.
The NTP protocol requires that one clock source be named the "system
peer" as the ultimate time source, and this chooses the best for that.
Basically, it chooses the one with the lowest stratum, breaking ties
using the root distance. However, there is an "anti-clock-hopping"
heuristic, so it will stick with the previous choice briefly.
This is in case you have two sources that are basically tied, the
allowance for clock drift could make the winner always the one you heard
from most recently.
If the previous system peer survives to this round, it will be kept as
the system peer until it starts losing consistently.
Step 6: Average the peers and apply the time correction.
If there's a PPS source, it is incorporated into the solution at this
stage, and marked with 'o', but I won't go into that.
The time corrections are averaged, weighted by the apparent quality,
and that is the final correction fed to the timekeeping PLL.
So ultimately, only peers marked '+' or '*' directly feed their values
into the locak clock, but everything is used as part of the competition
to select the best.
There is an arbitrary maximum is the limit on 10 peers going into
selection (because selection is expensive), but all clocks participate
in the earlier elimination rounds, so they do contribute in some way.
(Exercise for the student: If you've seen the movie "Entrapment",
you may recall that there's an elaborate stock market swindle based on
falsifying a satellite time code. Why would it not have worked if
they'd been using ntpd?)
_______________________________________________
timekeepers mailing list
[email protected]
https://fortytwo.ch/mailman/cgi-bin/listinfo/timekeepers
