[ratelimits] Remarks regarding the Knot DNS 1.2.0 RRL implementation

[Vernon Schryver]

> From: =?UTF-8?Q?Marek_Vavru=C5=A1a?= <marek.vavrusa at nic.cz>

> > the mapping of tuples to buckets is specified in the tech-note, and BIND9
> > RRL adheres to that mapping.
>
> Not exactly. As BIND9 RRL stores just qname hash (which is completely
> reasonable with me),
> it is possible to end up in the same bucket with a client asking for a
> different names.
> So should we store complete qnames in the tuples or should we accept
> false positives?

That's a misleading way to look at it.  The BIND9 RRL code has false
positives above 65536 requests/second/IP address according to the
birthday paradox for a 32-bit hash function, assuming the hash
function is good.  At 65K qps or even 1K qps from a single IP address,
something is wrong and rate limiting is not really a false positive.


A simple hash (no checking IP address and resetting counters) with
4,000,000,000 buckets and so a collision probability >0.5 only above
at a total 65K qps (not just per IP address) would also be ok.

A simple hash with only 10,000 buckets and so collisions at only
100 total qps would obviously be bad.

I think a simple hash with 1,000,000 buckets and so a collision
probability >0.5 at 1K total qps (not just per IP address) is bad,
but that is because I hear from people dealing with far, far more
than 1K qps and because BIND9 on a single modest CPU does more than
20K qps according to the RPZ sanity test.

If chaining were hard or expensive, one might argue that simple
hashing would be ok for small DNS servers.  I think the BIND9 code
shows that chaining is neither difficult nor expensive, and so I
could not accept that argument.


Vernon Schryver    vjs at rhyolite.com