Subject: [Ntp] Handling synchronization loops

From: Miroslav Lichvar <[email-masked]>
Date: Wed, 16 Feb 2022 15:29:30 +0100

There is a new version of my NTPv5 draft:
https://datatracker.ietf.org/doc/draft-mlichvar-ntp-ntpv5/

Beside some smaller improvements, it now specifies the Reference IDs
Request and Response extension fields using the 4096-bit Bloom filter
that was proposed by Daniel in his design.

NTPv5 clients should now be able to detect a synchronization loop over
any number of servers, even if they are not the best selected source
which in NTPv4 set the client's reference ID. 

However, I'm not sure what should exactly happen when the client
detects a loop. As there is a delay in the distribution of the
reference IDs, I suspect there is an instability in the selection.

Let's say we have 4 NTP clients in a local network configured in a
ring for "peering":

        +--------+         +--------+
        | Host A |---------| Host B | 
	+--------+         +--------+
            |                  |
            |                  |
        +--------+         +--------+
        | Host D |---------| Host C | 
	+--------+         +--------+

Each one is configured to poll some remote servers and two of its
local peers. We would like them to reach a stable state in the
selection, for example A->B->C->D, or A<-B->C->D.

If they are started at the same time, every host will first select
only the remote servers as the local servers are not synchronized yet.
Then on each link the direction of synchronization is selected
randomly depending on the order of their polling. There is no loop on
individual links (assuming the 4096-bit filter is not split over
multiple messages), but a loop can form over the whole ring, e.g:

A->B->C->D->A

after three polls they all see that they are in a loop. They unselect
the peer:

A  B  C  D  A

and we are back where we started.

I'm not sure if there is a guarantee a stable state will eventually be
reached if the polling order happens to be stable. There is also an
additional delay when the filter is exchanged in smaller parts. A loop
can form even between two hosts.

I think we might need to specify for how long should clients wait
before selecting a server that was in a loop again. This could be a
random number based on their polling interval, stratum, and the number
of polls it takes to exchange the whole filter. There could also be a
requirement for servers to delay removing reference IDs from their
filters.

For reference, in NTPv3 loops cannot form, because only sources with
lower stratum can be selected. That is too restrictive. In NTPv4 there
is a single reference ID, which can detect only loops between two
clients and only if one of them selected the other as the "system"
peer. Other loops are ignored and synchronization stops only when
stratum reaches 16.

Any suggestions?

-- 
Miroslav Lichvar

---

From: Danny Mayer <[email-masked]>
Date: Wed, 16 Feb 2022 17:39:09 -0500

> Let's say we have 4 NTP clients in a local network configured in a
What is being lost in all this is the fact that a host can respond on 
multiple interfaces. Thus ReferenceID's *cannot* be IP Addresses as is 
currently being done. A server *should* create an value that can be part 
of the packet that is sent out on ALL interfaces regardless of the type 
of packet. This ID would need to be added to the base packet. This can 
be a randomly generated ID but needs to be the same for the duration of 
the server. This can then be used for the referenceID sent in the 
packet. IP addresses only worked when there was only one interface and 
IP address. That's no longer a viable solution. If I'm getting ntp 
packets from a multicast NTP server what Reference ID would you want? It 
can't be the multicast address.

Danny

---

From: Hal Murray <[email-masked]>
Date: Wed, 16 Feb 2022 17:36:25 -0800

[email-masked] said:
> currently being done. 

Will is work if a system picks one of its IP Addresses?

> This can be a randomly generated ...

Do we want to hide or expose the upstream server?  An IP Address is handy for 
debugging.  Are there any privacy issues?

-- 
These are my opinions.  I hate spam.

---

From: Danny Mayer <[email-masked]>
Date: Wed, 16 Feb 2022 22:16:29 -0500

> Will is work if a system picks one of its IP Addresses?
The ReferenceID was never really an IP address. The IP address of the 
chosen truechimer was used even though it would be different on each 
interface address and got folded when it was an IPv6 address. This is 
madness. If it used a private IP address how could it help you?
> debugging.  Are there any privacy issues?
It's debatable whether or not it's helpful in debugging. You would need 
a proper tracing capability which currently would require mode 6 packets 
since none of the other modes would tell you its preferred reference server.

Danny

---

From: Steven Sommars <[email-masked]>
Date: Wed, 16 Feb 2022 21:50:41 -0600

I find the reference ID occasionally useful in debugging.   Currently I'm
monitoring several thousand public NTP servers.
Of those, 59 report reference ID=216.239.35.X, i.e., Google.  Many of these
public servers are in the NTP Pool, which could cause problems when (if?)
the next leap second occurs, since Google uses leap second smearing.   Of
these 59, only one responds to an ntp -np (mode 6) command.

If a stratum 2+ server goes haywire, the reference ID sometimes shows that
the server was syncing to a misbehaving upstream source, or bouncing
between several sources.

The debugging usage of the Reference ID exists but should not be a major
consideration in NTPv5, in my opinion.

Steve Sommars

On Wed, Feb 16, 2022 at 9:17 PM Danny Mayer <[email-masked]> wrote:

> _______________________________________________
> ntp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ntp
>

---

From: Harlan Stenn <[email-masked]>
Date: Wed, 16 Feb 2022 22:13:28 -0800

> can't be the multicast address.

I get that this is a theoretical problem.

Is it a *real* problem?

I'm not at all worried about the "I have multiple IPs/NICs" issue because:

- in the ~30 years' time I've been actively working with NTP, I have not
   heard of a single case where this has been an issue
- the NTP Project has already submitted a "suggested refid" proposal,
   which will also help with this

If it's clear that this is a REAL problem and not a hypothetical one, we 
can certainly look at this harder.

And given that "longer" loops mean larger stratum differences between 
the beginning and ending nodes in the loop and also increasing root 
distance, I suspect that this really isn't a problem for any "real" 
installation.

-- 
Harlan Stenn <[email-masked]>
http://networktimefoundation.org - be a member!

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 17 Feb 2022 08:33:49 +0100

On Wed, Feb 16, 2022 at 05:39:09PM -0500, Danny Mayer wrote:
> currently being done. A server *should* create an value that can be part of
> the packet that is sent out on ALL interfaces regardless of the type of
> packet.

Yes, that's how it works in the NTPv5 draft. Each server has a single
randomly generated 120-bit reference ID that it provides to its
clients together with reference IDs of its own direct and indirect
servers up to stratum 1.

With this, all loops can be detected. The question is what to do when
that happens. If it unselected the source for synchronization only
when it indicated a loop, it seems it could leep to flapping.

-- 
Miroslav Lichvar

---

From: "Ulrich Windl" <[email-masked]>
Date: Thu, 17 Feb 2022 08:36:22 +0100

>>> Miroslav Lichvar <[email-masked]> schrieb am 16.02.2022 um 15:29 in
Nachricht <Yg0KSjSKAFhnShaO@localhost>:
> https://datatracker.ietf.org/doc/draft‑mlichvar‑ntp‑ntpv5/ 
> 
> Request and Response extension fields using the 4096‑bit Bloom filter
>         +‑‑‑‑‑‑‑‑+         +‑‑‑‑‑‑‑‑+
>         | Host A |‑‑‑‑‑‑‑‑‑| Host B | 
> 	+‑‑‑‑‑‑‑‑+         +‑‑‑‑‑‑‑‑+
>             |                  |
>             |                  |
>         +‑‑‑‑‑‑‑‑+         +‑‑‑‑‑‑‑‑+
>         | Host D |‑‑‑‑‑‑‑‑‑| Host C | 
> 	+‑‑‑‑‑‑‑‑+         +‑‑‑‑‑‑‑‑+
> 

The first question for that scenario would be why yout don't "X-perr", too,
i.e.: A<->C and B<->D?

> selection, for example A‑>B‑>C‑>D, or A<‑B‑>C‑>D.

When <-> means peering, what exactly do "->" and "y-" mean?

> randomly depending on the order of their polling. There is no loop on

What exactly means "selected" here? If the external source has a lower
stratum, those external servers most likely will remain the reference(s).

> individual links (assuming the 4096‑bit filter is not split over
> A‑>B‑>C‑>D‑>A

If this should describe a synchronization path (exteremly unlikely IMHO), that
would be (say a got ist time from X at stratum-1):
A would be startum-2
B would be startum-3
C would be startum-4
D would be startum-5
A synchronized indirectly from X via B,C, and D would be startum-6 (1st
iteration of the loop)
If the "loop continues" B would be at 7, C would be at eight, ...

As long as any of the servers has access to an external source, it's very
unlikely this will occur.

The more interesting case would be if you consider two stratum-1 sources X and
Y that are configured as sources for A through D, and a lower level (say E,F,G)
has configured the A though D as sources. How can E-G make sure when selecting
different sources from A-D that they are really "fed" from different sources,
that is: While thinking there are multiple sources, there actually may be just
one.

> and we are back where we started.

I think the important point is (hopefully we agree) that through such a loop
the time quality becomes worse and it has to be reflected in some numbers.
So the worse time should help to break the loop when any better sources are
around. If not the synchronization system will "fall apart"; that's how it is
in NTPv3 and v4.

> can form even between two hosts.

The stable state (with the conditions mentioned above) is: "every node at
stratum-16" (unsync)

> peer. Other loops are ignored and synchronization stops only when

Describe a more realistic loop that can cause problems in practice.
For that would mean the system thinks it has good time, but actually does
not.

Regards,
Ulrich Windl

> ‑‑

---

From: "Ulrich Windl" <[email-masked]>
Date: Thu, 17 Feb 2022 11:33:32 +0100

>>> Harlan Stenn <[email-masked]> schrieb am 17.02.2022 um 07:13 in Nachricht
<[email-masked]>:
...
>    heard of a single case where this has been an issue

Maybe revisit NTP's bugzilla ;-)

Regards,
Ulrich Windl

---

From: "Ulrich Windl" <[email-masked]>
Date: Thu, 17 Feb 2022 11:45:01 +0100

>>> "Ulrich Windl" <[email-masked]> schrieb am 17.02.2022 um
08:36 in Nachricht <[email-masked]>:
...
> The first question for that scenario would be why yout don't "X-perr", too,

Sorry: The first question for that scenario would be why you don't "X-peer", too,

...

---

From: Daniel Franke <[email-masked]>
Date: Thu, 17 Feb 2022 06:04:14 -0500

I think Danny is right that some more information needs to go into the
base packet, though. The base packet should include the server's
reference ID, and a sequence number which increments every time the
Bloom filter changes. Not only is it unreliable to assume that
distinct IP addresses correspond to distinct servers, it's likewise
unreliable to assume that the same server will still be at the same IP
address after another polling interval has elapsed. The Bloom filter
is bulky and we don't want to be including it in every exchange, so
clients need to know when to request an update. Any change to the
reference ID and/or the sequence number is the signal that they should
do so.

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 17 Feb 2022 12:24:16 +0100

> reference ID and/or the sequence number is the signal that they should

The reference IDs are randomly generated. There are no IP addresses
involved unless there is an older NTP version, in which case the
reference ID is the MD5 sum of the address.

Using sequence numbers and transferring the bloom filter only when it
changes would make the message length variable, which impacts
stability of the NTP delay and quality of filtering. I expect the
filter will change frequently as it includes all combined sources, not
just the system peer.

In my draft the filter can be transferred in smaller pieces to make
the messages shorter, but still constant. It just adds a delay. With
the sequnce number there would be delay too.

-- 
Miroslav Lichvar

---

From: Daniel Franke <[email-masked]>
Date: Thu, 17 Feb 2022 06:29:19 -0500

My expectation is that messages which include the Bloom filter will be
used *only* for communication of the Bloom filter and not for time
synchronization. This eliminates any problems associated with variable
message length.

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 17 Feb 2022 12:51:03 +0100

> synchronization. This eliminates any problems associated with variable

Ok, that could work, but we should consider the increase in the
average rate of NTP messages and the temporary network and
timestamping load that will happen with each change of the filter.
This would be the first non-timing NTP message. In PTP, there is a
separate port for that.

-- 
Miroslav Lichvar

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 17 Feb 2022 13:19:29 +0100

> The first question for that scenario would be why yout don't "X-perr", too,

To keep it simple. If you mesh everything, there is a much larger
number of loops that could form.

> When <-> means peering, what exactly do "->" and "y-" mean?

A->B means that B is synchronizing to A, i.e. ntpq would print the
source with the * or + symbol.

A<->B would be a loop.

> stratum, those external servers most likely will remain the reference(s).

The remote server will be selected as the system peer (* symbol), but
the local servers will likely be combined with the system peer too (+
symbol).

> If the "loop continues" B would be at 7, C would be at eight, ...

That would happen if the remote server stopped working. We want to
prevent them from getting to the maximum stratum. That's a failure,
quite common with NTPv4, and the reason why we don't recommend more
than 2 peers to form a full mesh, but rather a line.

> unlikely this will occur.

The idea was to prevent all synchronization loops, not just through
the system peers (* symbol).
> that is: While thinking there are multiple sources, there actually may be just

That's a different problem, but the bloom filter could help with that
too. If the clients see that the number of different bits in the
filters coming from A-D is small, they could decrease their weight in
favor of other sources.

> around. If not the synchronization system will "fall apart"; that's how it is

The idea was that in NTPv5 we can detect all loops and avoid "falling
apart".

-- 
Miroslav Lichvar

---

From: "Ulrich Windl" <[email-masked]>
Date: Thu, 17 Feb 2022 14:50:27 +0100

>>> Miroslav Lichvar <[email-masked]> schrieb am 17.02.2022 um 12:51 in
Nachricht <Yg42p5qmuww2v7Qt@localhost>:
> On Thu, Feb 17, 2022 at 06:29:19AM ‑0500, Daniel Franke wrote:
> This would be the first non‑timing NTP message. In PTP, there is a
> separate port for that.

Maybe just re-bless the mode-6 protocol and let ntpd use (enhanced) mode-6
messages to learn about the bloom filter. That could be done completely
independent of timing messages, and you don't even need a new port ;-)
So far it was not forbidden for ntpd to use mode-6 messages, even if it never
was done.

Regards,
Ulrich

---

From: "Ulrich Windl" <[email-masked]>
Date: Thu, 17 Feb 2022 15:03:03 +0100

>>> Miroslav Lichvar <[email-masked]> schrieb am 17.02.2022 um 13:19 in
> source with the * or + symbol.

I think whether * or + makes a difference.

> A<->B would be a loop.

Also I'd think it means "peering", not "loop".

Just an idea:
A->B: B has configured A as source
A=>B: B has selected A as source
A=*>B: B selected A as preferred source

A<->B: A and B are configured as peers
A<=>B: A and B selected each other as peer
...more?...

> than 2 peers to form a full mesh, but rather a line.

With the external servers being reachable by A-D, I really see no loop (all
peers at same stratum), "alternate feed" (for the same source) maybe, but no
loop.

>> The more interesting case would be if you consider two stratum-1 sources X

> and
>> around. If not the synchronization system will "fall apart"; that's how it

> is

OK, I still have to learn about that feature.

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 17 Feb 2022 14:11:47 +0000

As a general rule, the IETF doesn't like putting additional IP addresses in protocol messages.  Note to say that it couldn't be done, but if so there should be a rationale for it to shirt-circuit IESG questions you'll get.

---

From: Dan Drown <[email-masked]>
Date: Thu, 17 Feb 2022 08:12:19 -0600

> synchronization. This eliminates any problems associated with variable

This seems fine to me, but what about the case of an anycast NTP  
server address? The query for the reference filter could go to a  
different server than the time query. Is that a case worth solving?

---

From: Danny Mayer <[email-masked]>
Date: Thu, 17 Feb 2022 09:22:36 -0500

> source with the * or + symbol.
That would only be possible to see if you allow mode 6 packets...
> than 2 peers to form a full mesh, but rather a line.
Who is the "we" here in the sentence "we don't recommend"? This is no 
reason to limit the number of peers. The NTP server is perfectly capable 
of handling that.
> the system peers (* symbol).
How are you going to even see that without mode 6 packets? One of the 
issues that you need to be able to grapple with is how you are going to 
be able to monitor your servers? You won't even know you have a 
synchronization loop without it.
> The idea was that in NTPv5 we can detect all loops and avoid "falling
You are more likely to have dropped the server with the synch loop by 
that time because the quality of the results would be so bad.

Danny

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 17 Feb 2022 16:42:24 +0100

> I think whether * or + makes a difference.

The only difference between * and + is that the source marked with *
determines the client's stratum and NTPv4 reference ID. For the actual
synchronization of the clocks there is no difference. They all
contribute to the update of the client's clock. 

Let's make an even simpler example of a synchronization loop with just
two clients (A and B) in a local network polling each other and a
remote server (R).

The ntpq -p output on A could be:
     remote           refid      st t when poll reach   delay   offset  jitter
==============================================================================
*10.1.123.1      LOCAL(1)         1 u  108  512  377   20.505   +1.018   0.083
+192.168.123.2   10.1.123.1       2 u   88  512  377    0.203   +1.220   0.245

on B:
     remote           refid      st t when poll reach   delay   offset  jitter
==============================================================================
*10.1.123.1      LOCAL(1)         1 u  143  512  377   20.502   -0.298   0.233
+192.168.123.1   10.1.123.1       2 u  124  512  377    0.213   -1.243   0.235

There is a synchronization loop between A and B, because they both
have selected the other one for synchronization (+ symbol). NTPv4
cannot prevent that, because it provides to clients only the reference
ID of the system peer (*).

To demonstrate how is that a problem we can observe what happens when
a 10ms time step is injected on A. With the loop there are reflections
coming back from B causing instability:

https://i.imgur.com/cWcLMVD.png

This can happen over any number of clients, not just two.

If we remove the loop (i.e. configure A to not poll B), we can see
that the response is much better:

https://i.imgur.com/xv155Cv.png

The new feature proposed for NTPv5 is that it will detect all loops
using the Bloom filter. My question is what should clients do when a
loop is detected to stabilize the selection.

-- 
Miroslav Lichvar

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 17 Feb 2022 16:49:32 +0100

On Thu, Feb 17, 2022 at 09:22:36AM -0500, Danny Mayer wrote:
> How are you going to even see that without mode 6 packets? One of the issues
> that you need to be able to grapple with is how you are going to be able to
> monitor your servers? You won't even know you have a synchronization loop
> without it.

Please see the draft that was linked in the original post. There is a
Bloom filter which contains reference IDs of all servers up to the
primary time sources.

With mode 6 you would need to request information recursively over the
servers. That would be a huge waste of bandwidth and security issue.

-- 
Miroslav Lichvar

---

From: Hal Murray <[email-masked]>
Date: Thu, 17 Feb 2022 16:05:37 -0800

> My question is what should clients do when a loop is detected to stabilize
> the selection.

Make a graph, with arrows from clients to their servers.  If you put the lower 
stratum servers on top, the arrows will generally point up.  If there is a 
loop, there will be a path through the graph that only uses the forward 
direction of the arrows.

Take your example.  There would be 2 arrows up and 2 horizontal.  The way to 
break that loop is to have A and B flip a coin and remove one of those 
horizontal arrows.

You could have a similar setup with a large loop, all at the same stratum.  
Again, somebody has to delete one of those arrows.  A simple way to decide 
would be to compare the reference IDs.  The server with the lowest ID would 
delete its arrow.  An alternative would be that the last system to join, the 
one setting up the loop, doesn't join.

That leaves the problem of arrows going down, for example a stratum 3 client 
using a stratum 4 server.  A simple rule is "Don't do that."  That client can 
either remove its down link or demote itself to stratum 4 turning that link 
into horizontal.

---------

Note that the Bloom filter only has to cover servers at the same stratum.  If 
long chains are not common, it may be simpler/cleaner to pass around a list of 
servers rather than use a Bloom filter.

Does anybody have any statistics?  Even if the chains are short, the fan-out 
can be large and you have to send the whole tree so a system can see if it is 
in it.  A fanout of 5 and depth of 3 is 125 leaf nodes.  At 8 bytes per ID, 
that's 1K bytes.

--------

Note that client-only systems are easy.  They can never be part of a loop 
since there are no arrows pointing in to them.  Thus there is no need for any 
anti-loop logic or traffic.

-------

There is a potential terminology problem in this area.  The config file for 
the Mills code uses "peer" to setup a symmetric relation with arrows in both 
directions and "server" to setup a client/server relation with only one arrow.

---

From: "Ulrich Windl" <[email-masked]>
Date: Fri, 18 Feb 2022 08:37:11 +0100

>>> Miroslav Lichvar <[email-masked]> schrieb am 17.02.2022 um 16:42 in
Nachricht <Yg5s4JXhpHRAGZvd@localhost>:
>> >> When <‑> means peering, what exactly do "‑>" and "y‑" mean?
>> > 
>> > A‑>B means that B is synchronizing to A, i.e. ntpq would print the
> The ntpq ‑p output on A could be:
============================================================================
> ==
============================================================================
> ==
> *10.1.123.1      LOCAL(1)         1 u  143  512  377   20.502   ‑0.298   
> 0.233
> +192.168.123.1   10.1.123.1       2 u  124  512  377    0.213   ‑1.243   
> 0.235
> 
> 

Honestly I never considered such as a loop; instead I'd call it non-optimal
peering.
Each f the two syncs from 10.1.123.1, so there is no loop. It is OK to
consider the other peer, too, even if those get their time from the same
source.
It's even possible that the path A->B->Reference gets better statistics than
A->Reference (maybe due to some odd network jitter). But still that is no
loop.
For me a loop is when servers repeatedly sync from each other (via preferred
source), not if there are indirect contributions from the same source.

Is there an agreement on this?

The NTPv4 spec only has a code comment saying:
        /*
         * A loop error occurs if the remote peer is synchronized to the
         * local peer or the remote peer is synchronized to the current
         * system peer.  Note this is the behavior for IPv4; for IPv6
         * the MD5 hash is used instead.
         */
So (to use my notation) if you have A<=R, B<=R, and A<=>B then it would be
considered to be a loop?

Even in NTPv3 a "loop" is never formally specified; instead it claims:
"synchronization subnet topology should be organized to produce
the highest accuracy, but must never be allowed to form a loop."

To at least the NTPv5 specification should formally define what a
synchonization loop is.
In my simple view I see it as a graph where a client-server association is a
one-way valve (from server to client), while a (working) peer association is a
two-way connection.
So if you add water at the references (stratum-1) a loop would exist if you
see water circling anywhere in the graph. IMHO in the scenario above the water
might oscillate between A and B, but it will never circle, so it is no loop
IMHO.

> a 10ms time step is injected on A. With the loop there are reflections

How exactly is it injected?

> This can happen over any number of clients, not just two.

Is it an instability, or is it a loop?
With just two sources A may not be able to detect B as outlyer or
falseticker.

> loop is detected to stabilize the selection.

Maybe start with formally defining what a "loop" is.

Regards,
Ulrich

---

From: Miroslav Lichvar <[email-masked]>
Date: Mon, 21 Feb 2022 10:48:27 +0100

On Thu, Feb 17, 2022 at 04:05:37PM -0800, Hal Murray wrote:
> Make a graph, with arrows from clients to their servers. 

With the bloom filter there is no way to make a graph. All reference
IDs are hashed and ORed together. There are no strata.

We can consider replacing it with an extension providing the full
graph. That was the original idea. To save bandwidth, it could
describe changes between different versions of the graph, e.g. when a
small number of servers is added or removed.

> either remove its down link or demote itself to stratum 4 turning that link 

That would be a good idea to test. I suspect it might not be very
stable as the stratum of a server can change easily if its sources
have a similar root distance (clock hopping).

> in it.  A fanout of 5 and depth of 3 is 125 leaf nodes.  At 8 bytes per ID, 

It would be great to have some statistics about this, but with mode 6
being blocked everywhere I'm not sure how could we get it.

-- 
Miroslav Lichvar

---

From: Miroslav Lichvar <[email-masked]>
Date: Mon, 21 Feb 2022 11:10:00 +0100

> Honestly I never considered such as a loop; instead I'd call it non-optimal

Peering is a configuration detail. What matter is that A is polling B
and B is polling A. If A selects B for synchronization and B selects A
for synchronization at the same time, a loop has formed between A and
B. They can be both synchronized to another source, which makes the
impact of the loop between A and B weaker, but it is still there.

> How exactly is it injected?

The clock was stepped by 10 ms.

> Is it an instability, or is it a loop?

A loop which caused an instability.

> Maybe start with formally defining what a "loop" is.

A synchronization loop is when a clock is being synchronized to
itself, over zero, one, or more other clocks.

The shortest loop is when a client is synchronizing to itself:
A->A

Two clients synchronizing to each other:
A->B->A

Three clients synchronizing in a loop:
A->B->C->A

A client can be synchronized to multiple sources. It doesn't matter if
the source is marked as * or +. A loop can go through any source.

-- 
Miroslav Lichvar

---

From: "Ulrich Windl" <[email-masked]>
Date: Tue, 22 Feb 2022 13:13:26 +0100

>>> Miroslav Lichvar <[email-masked]> schrieb am 21.02.2022 um 11:10 in
Nachricht <YhNk+HnH58jCR1hT@localhost>:
>> Honestly I never considered such as a loop; instead I'd call it
non‑optimal
> impact of the loop between A and B weaker, but it is still there.

I still think time will go "ping-pong", but not loop. Also if A is at stratum
X, B will be X+1, and then A will be X+2 (if really syncing from B), and B will
be X+3 then, and so on.
So the loop will break when one reaches stratum 15.

> A‑>A
> A‑>B‑>A
> A‑>B‑>C‑>A

---

From: Hal Murray <[email-masked]>
Date: Thu, 24 Feb 2022 21:24:42 -0800

[email-masked] said:
> With the bloom filter there is no way to make a graph. All reference IDs are
> hashed and ORed together. There are no strata.

> We can consider replacing it with an extension providing the full graph. That
> was the original idea. To save bandwidth, it could describe changes between
> different versions of the graph, e.g. when a small number of servers is added
> or removed. 

Let's ignore how the data is passed around for now and focus on what we need 
to pass around.

Suppose we start with a running system and each server has a full graph of its 
upstream servers.  What would a new server need to know to join?  If using one 
of the new server links would make a loop, how do we decide if the new server 
should drop that link or some link in the established system should be 
dropped?  A variation on that is a link coming back up.  Or maybe that's all 
we need.  A new server is just a bunch of links coming up.

Do we need to avoid all loops?  Assume that a server derives the target time 
with some weighting of its upstream servers.  If a loop would contribute less 
than X%, is that good enough?  What is a reasonable value of X?  I was 
thinking that this might allow us to trim the size of the tree that each 
server has to keep track of and distribute.  I expect that sereral of the 
truncated ends could merge together and add up to a server being over X?

-----------

There are 2 reasons to use a server.  One is to get good time.  The other is 
to sanity check the real server(s).

Can we reduce the size of the graph that has to be passed around if we 
explicitly mark some servers as check-only?  Would that be worth the 
additional complexity?

-----------

This discussion has focused on loops.

Do we also want to investigate other weak links?  For example depending on a 
single stratum 1 server.  I expect the logic for that will also catch cases 
where everything funnels through a single server at other levels.

Should we keep track of NTS vs unauthenticated links?  But authenticated 
doesn't actually tell us anything about the quality of a clock.  We can 
probably figure out if the time is good using NTP.  By "quality", I'm 
interested in the reliability of the people running the server.

-----------

How much trouble could a bad guy generate by pretending to be a server and 
asking to break all sorts of important links because they will cause a loop?

This all seems too complicated.  Is there something else we can do?

Miroslav: You had good graphs with a simple loop.  Can you make another one 
with a longer loop?

-----------

Clients don't need to worry about loops.

There is another potentially large class of servers that can't contribute to loops.  I'm thinking of servers in a medium size company.  The idea is to reduce the load on the network servers.  Those servers can't contribute to any loops if they don't answer requests from "outside".

---

From: "Ulrich Windl" <[email-masked]>
Date: Fri, 25 Feb 2022 09:28:25 +0100

>>> Hal Murray <[email-masked]> schrieb am 25.02.2022 um 06:24 in
Nachricht

> ‑‑‑‑‑‑‑‑‑‑‑

> explicitly mark some servers as check‑only?  Would that be worth the 
> additional complexity?
> 
> ‑‑‑‑‑‑‑‑‑‑‑
> 

> where everything funnels through a single server at other levels.

Hi!

If you have a look at the image attached (showing some potential time sync
network for an intranet with maybe a "few holes drilled into a firewall"), are
there really timing loops?
Or are the multiple stratum-2 servers just giving the impression there are
more references than there actually are? The idea is that the stratum-2 servers
build some stable layer for the clients to choose from, while some clients also
might want to peer (e.g. nodes in a cluster).
By Miroslav's definition that would be full of "timing loops". Agreed, it's
possible that all stratum-3 clients effectively sync from the same stratum-1
via different paths, but if you have only one or two sources in your network?

> ‑‑‑‑‑‑‑‑‑‑‑

> ‑‑‑‑‑‑‑‑‑‑‑
> There is another potentially large class of servers that can't contribute to

> loops.  I'm thinking of servers in a medium size company.  The idea is to 
> reduce the load on the network servers.  Those servers can't contribute to 
> any loops if they don't answer requests from "outside".
> 
> 
> ‑‑

---

From: Hal Murray <[email-masked]>
Date: Fri, 25 Feb 2022 02:53:03 -0800

[email-masked] said:
> network for an intranet with maybe a "few holes drilled into a firewall"),
> are there really timing loops? 

There aren't any arrows on your diagram.

Assuming that the S3-S2 lines and S2-S1 lines are arrows going up, the 
question is what happens to the horizontal lines.  If those lines are 
bidirectional, that's a loop.

---

From: "Ulrich Windl" <[email-masked]>
Date: Fri, 25 Feb 2022 12:19:29 +0100

>>> Hal Murray <[email-masked]> schrieb am 25.02.2022 um 11:53 in
Nachricht
<[email-masked]>:

> [email-masked]‑regensburg.de said:

;-)

Obviouly the top is stratum-1, and the lower levels sync from the above (as
client), while they are peering horizontally (the green lines).
I thought the "arrows" are obvious.

> 
> Assuming that the S3‑S2 lines and S2‑S1 lines are arrows going up, the 

(For the following let me refer to the time references as R1 to R3 (left to
right), the stratum-1 as A1-A3, stratum-2 as B1-B3, and so on)

OK, if I understood Miroslavs algorithm correctly, none of A1-A3 would select
R2 if any peer had selected it (DCF-77 and GPS are local, thus unsharable).
Likewise B1-B3 would refuse any of A1-A3 that use the same time reference, and
they would refuse to peer with any of such. So each of B1-B3 would have at most
one distinct of A1-A3.
Likewise C1-C3 would select only one distinct server out of B1-B3 each, and
they would refuse to peer with any other C1-C3.
So does that really improve the time at the C1-C3 level?

It seems Miroslav's algorithm prefers the "many time references to few
clients" while I thought the original idea was "few references to many
clients".

Regards,
Ulrich Windl

---

From: Hal Murray <[email-masked]>
Date: Fri, 25 Feb 2022 03:49:35 -0800

> R2 if any peer had selected it (DCF-77 and GPS are local, thus unsharable).

No.  The arrows from A to R all go up.  To make a loop, you need to find a 
path where you follow the forward direction of all the arrows in the path and 
get back to your starting point.  If the arrows from A to R all go up, you 
can't get back down to your starting point.

The loops in your diagram are A1->A2->A1 and similar.

---

From: "Ulrich Windl" <[email-masked]>
Date: Fri, 25 Feb 2022 13:35:23 +0100

>>> Hal Murray <[email-masked]> schrieb am 25.02.2022 um 12:49 in
Nachricht
<[email-masked]>:

>> right), the stratum‑1 as A1‑A3, stratum‑2 as B1‑B3, and so on)
> 
>> OK, if I understood Miroslavs algorithm correctly, none of A1‑A3 would
select
>> R2 if any peer had selected it (DCF‑77 and GPS are local, thus
unsharable).
> can't get back down to your starting point.

If the arrows go like "server --> client", the I don't understand.

> 
> The loops in your diagram are A1‑>A2‑>A1 and similar.

OK, but taking Miroslav's algorithm serious: If GPS is a reference, then only
one server in the world is allowed to sync to GPS, as otherwise there would be
a loop?
Or in other words: Where would peering be allowed then?

Regards,
Ulrich

---

From: Hal Murray <[email-masked]>
Date: Fri, 25 Feb 2022 05:20:22 -0800

> If the arrows go like "server --> client", the I don't understand.

I was drawing the arrows from client to server -- generally up for the way 
that most of us draw things with low stratum on top.  You can draw them the 
other way around if you want but then you have to flip some up/down in my text.

> one server in the world is allowed to sync to GPS, as otherwise there would
> be a loop?

I don't understand your problem.  If lots of clients use a server, all the 
arrows go up, there is no way to make a loop.  Start at a client, go up to the 
server.  There are no down arrows, thus no way to make a loop with that start.

> Or in other words: Where would peering be allowed then?

It's not.  That's assuming you mean the symmetric (bidirectional) connection 
that is setup if you say "peer" in your config file in the Mills code.  You 
can also make a loop if both servers use each other with a "server" in the 
config file.

--------

Let me try again.  Draw arrows between your collection of NTP boxes from 
client to server.  If there is a loop, you will be able to find a path through 
that graph that goes forward following arrows and gets back to the start.

If you have a simple layered setup like your R, A, B picture, draw arrows "up" 
from A to R and B to A.  I'm assuming there are no client-server connections 
from any server to a server of higher stratum.  They would be down arrows in 
the diagram.

If there are no R-R, A-A, or B-B connections, you can't find a loop.  All you 
can do is go up.

If you add connections at the same stratum level, you have to be careful or 
you will make a loop.
  A "peer" from A1<-->A2 would make a loop.
  A1-->A2-->A3-->A1 would also make a loop.
  But flip the direction of any one of those 3 connections and you break the 
loop.
  A1-->A2-->A3<--A1 is OK.

Yes, it''s ugly.  If you don't want loops, you can't setup the obvious 
everybody-peers-with-everybody at the same stratum that seems like the obvious 
way to do things (for a few servers at that stratum).

---

From: "Ulrich Windl" <[email-masked]>
Date: Mon, 28 Feb 2022 08:32:55 +0100

>>> Hal Murray <[email-masked]> schrieb am 25.02.2022 um 14:20 in
Nachricht
<[email-masked]>:

>> If the arrows go like "server ‑‑> client", the I don't understand.
> 
> I was drawing the arrows from client to server ‑‑ generally up for the way 

> ‑‑‑‑‑‑‑‑
> from A to R and B to A.  I'm assuming there are no client‑server connections

> 
> the diagram.
> 
> If there are no R‑R, A‑A, or B‑B connections, you can't find a loop.  All
you 

> you will make a loop.
>   A "peer" from A1<‑‑>A2 would make a loop.
>   A1‑‑>A2‑‑>A3‑‑>A1 would also make a loop.

>   A1‑‑>A2‑‑>A3<‑‑A1 is OK.
> everybody‑peers‑with‑everybody at the same stratum that seems like the
obvious 
> way to do things (for a few servers at that stratum).

Hal,

I think I understand your arguments, but still I wonder:
IMHO that means "peering" ("peer" keyword) causes a loops in almost any case.
the only exception would be if all the individual peers have a completely
disjunct selection of reference clocks (which is close to impossible to
guarantee in practice).
I also think Miroslav's loop discussion ignores the stratum-effect (any server
X getting time from Y will have a stratum one higher than Y has) that will not
initially prevent "loops" (as you call them), but will break them after a few
iterations.

For example this configuration will have many loops according to Miroslav's
definition:
172.20.16.19# ntpq -pn
     remote           refid      st t when poll reach   delay   offset 
jitter
==============================================================================
 127.127.1.0     .LOCL.          14 l   6d   64    0    0.000   +0.000  
0.000
 239.192.123.11  .ACST.          16 a    -   32    0    0.000   +0.000  
0.000
 239.192.123.12  .ACST.          16 a    -   32    0    0.000   +0.000  
0.000
 239.192.123.21  .ACST.          16 a    -   64    0    0.000   +0.000  
0.000
 239.192.123.22  .ACST.          16 a    -   64    0    0.000   +0.000  
0.000
+172.20.16.16    172.20.2.25      2 s  166  256  377    0.203   +0.049  
0.078
+172.20.16.18    172.20.2.25      2 s  232  256  377    0.212   +0.005  
0.056
-172.20.16.18    172.20.2.25      2 u  502  512  377    0.172   +0.013  
0.040
*172.20.2.25     .GPS.            1 u  507  512  377    0.124   -0.026  
0.054
+172.20.2.24     .DCFp.           1 u   14  512  377    0.208   -0.084  
0.014
+172.20.16.14    172.20.2.25      2 u   57  512  377    0.197   -0.058  
0.034
+172.20.16.13    172.20.2.25      2 u   25  512  377    0.143   -0.056  
0.052

172.20.16.18 # ntpq -pn
     remote           refid      st t when poll reach   delay   offset 
jitter
==============================================================================
 127.127.1.0     .LOCL.          14 l  92h   64    0    0.000   +0.000  
0.000
 239.192.123.11  .ACST.          16 a    -   32    0    0.000   +0.000  
0.000
 239.192.123.12  .ACST.          16 a    -   32    0    0.000   +0.000  
0.000
 239.192.123.21  .ACST.          16 a    -   64    0    0.000   +0.000  
0.000
 239.192.123.22  .ACST.          16 a    -   64    0    0.000   +0.000  
0.000
+172.20.16.16    172.20.2.25      2 s   19  256  377    0.192   +0.022  
0.021
+172.20.16.19    172.20.2.25      2 s   71  256  377    0.201   +0.000  
0.050
+172.20.16.19    172.20.2.25      2 u  173  512  377    0.234   +0.009  
0.024
+172.20.16.14    172.20.2.25      2 u  300  512  377    0.127   -0.086  
0.041
*172.20.2.25     .GPS.            1 u   39  512  377    0.165   -0.035  
0.034
+172.20.2.24     .DCFp.           1 u  291  512  377    0.195   -0.069  
0.047

IMHO this configuration actually improves the time on the peers in case there
is network jitter between the peers and the GPS or DCFp.
Accasionally ntp actually prefers DCF over GPS.

A more significant problem is that NTP cannot handle the situation where a
server explicitly configured as "peer" (s) will be also added via manycast
(u):
IMHO it should ignore sources learned via manycast when those associations are
there alsready, but that's a completely different problem.

Regards,
Ulrich

---

From: Hal Murray <[email-masked]>
Date: Sun, 27 Feb 2022 23:55:33 -0800

[email-masked] said:
> I think I understand your arguments, but still I wonder: IMHO that means
> "peering" ("peer" keyword) causes a loops in almost any case. the only
> exception would be if all the individual peers have a completely disjunct
> selection of reference clocks (which is close to impossible to guarantee in
> practice). 

No, as soon as you say "peer" in the config file you have setup a loop.  It 
doesn't depend on any refclocks or other servers.

> I also think Miroslav's loop discussion ignores the stratum-effect (any
> server X getting time from Y will have a stratum one higher than Y has) that
> will not initially prevent "loops" (as you call them), but will break them
> after a few iterations. 

That "break after a few iterations" only happens if there are no connections 
to stratum 1 servers, possibly through multiple hops.

> is network jitter between the peers and the GPS or DCFp. Accasionally ntp
> actually prefers DCF over GPS. 

I wasn't saying anything about whether a setup with a loop was better than one 
without, just describing how to discuss them and detect them.

Miroslav's graphs seemed very interesting.  I haven't tried to reproduce them 
or more complicated loops.