Re: [Ntp] NTPv5 Loop Detection without Stratum

[Miroslav Lichvar <[e-mail]>]

On Wed, Aug 24, 2022 at 08:35:39AM +1000, Paul Gear wrote:
> I'm far from an expert on bloom filters, but they can have false positives,
> which would result in a source which was not part of a client's upstreams
> being erroneously flagged as being so.  Would this not require a trace (like
> what Heiko has described above) to detect?

I'm not an expert either. To me it seems that it shouldn't be a
problem unless we expect the number of IDs to grow to several
hundreds.

With the proposed filter (m=4096 and k=10) the chances of a collision
are about:
- 1e-12 with 26 IDs
- 1e-10 with 43 IDs
- 1e-8 with 70 IDs
- 1e-6 with 118 IDs
- 1e-4 with 207 IDs
- 1e-2 with 408 IDs
- 1e-1 with 648 IDs

I guess we could get away even with a smaller filter, but this is
going to be difficult to estimate.

> In some cases, false positives would be inconsequential (e.g. when the
> client is using a well-served zone in the public pool and can easily ask for
> another source), but in private networks where the number of sources may be
> more limited discarding an upstream source may be more problematic.

Would those clients in a private network be expected to operate as a
server? If not, they don't need to check for loops.

-- 
Miroslav Lichvar