[ratelimits] defaults for DNS-RRL

[Vernon Schryver]

> From: Daniel Stirnimann <stirnima at switch.ch>

> >>   // set to max.  of query load the server can handle x WINDOW
> >>   max-table-size 1000000;
> > 
> > The documentation suggests that the table size should be about
> > the query rate per second, not per window.
>
> You are right, the documentation suggests to set it only to about the
> query rate per seconds.

In the BIND9 RRL implementation, it makes no sense to size the table
by "window", because every state blob with a non-negative tokent
count is garbage after one second.  Only state blobs with negative
counts and so representing streams of responses that are currently
being dropped or truncated are valid after one second.  There are
never more than a tiny handful of such state blobs.  In addition, every
state blob that has a negative count effective reduces the number
of other state blobs.  For example, a DNS server receiving 1000 qps
of which 100 are identical needs only 901 state blobls.


>                         I got the other definition from the paper
> "Defending against DNS reflection amplification attacks",
> http://www.nlnetlabs.nl/downloads/publications/report-rrl-dekoning-rozekrans.pdf
>
> "MAX-TABLE-SIZE RRL needs to keep state of the unique responses in order
> to be able to assign penalties. This entry sets the maximum amount of
> entries (called state blobs) which can be stored at the same time. This
> should be set to the product of the window size and maximum queries per
> second. 10000 state blobs should take about one megabyte of server
> memory. MaxQPS Window = Tablesize."

Those who know the NSD RRL implementation might want to explain that.

My somewhat wild guesses based on ignorance of the NSD RRL implemetation
are that in that implementation, either "window" does something different
than in the BIND9 iplementation, the basic rate limiting algorthm
differs, or that text is about the NSD RRL requirement for its hash
table to far larger than the query rate per second to minimize collisions
and so minimize false negatives that can result from resetting the
counter in a collision.

If the size NSD RRL hash table (i.e. the number of state blobs) is
not significantly larger the query rate, then there will be many
collisions.  Some of the collisions will involve several unrelated
responses colliding in single state blobs, and so falsely reseting
the count in the blob.  A load factor of 10% (i.e. ten times as many
state blobs as the query rate per second) sounds minimal.

In the BIND9 RRL implementation, a hash bucket can have many state
blobs, and so hash collisions cost time instead of accuracy.  When the
average number of state blobs per bucket gets too high, the BIND9 RRL
code expands the hash table, subject to the max-table-size limit.


Vernon Schryver    vjs at rhyolite.com