[ratelimits] Remarks regarding the Knot DNS 1.2.0 RRL implementation

[Vernon Schryver]

> From: Matthijs Mekking <matthijs at nlnetlabs.nl>

> We already do some sort of collision detection by checking whether the
> classification and the address range match. We also log this, although
> from the logs it is not really clear that it was due to a collision.
>
> We could add the full hash to the bucket and detect whether the
> collision was due to a hash collision or "bucket collision". In our
> default configuration that would add a little less than 4 MB in memory.

Oh!  Now I remember the private discussions last year with Wouter,
and that were later inaccurately summarized to this mailing list.
(I was tired of arguing, the inaccuracies were not too bad, and so
I did not protest the summmary.)

You only detect collisions between differing client IP addresses.
As discussed, a recursive resolver or a set of resolvers behind NAT
or load balancers at large ISPs that make many requests for different
(qtype,qname) can have undetected collisions.

I've spent time searching my mail archives, and see a possibly
greater problem than false positives due to undetected collisions
is false negatives due to the resetting after detected collisions.

If you care, I could send out my mail archives, but it would
probably be better for you to talk to Wouter.  I think he understood
my position.  I have the impression that he was considering adding
chaining.


Note that the BIND9 RRL code can also have undetected collisions or
false positives because only a 32-bit hash of the qname is saved and
checked.  However, to trigger BIND9 RRL undetected collsion with more
than probability greater than 0.5, DNS clients must send more than
2000 requests/second/CIDR block (square root of 2**32).


Vernon Schryver    vjs at rhyolite.com