[bind10-dev] ACL Syntax proposal

Michal 'vorner' Vaner michal.vaner at nic.cz
Mon May 30 15:58:12 UTC 2011


On Mon, May 30, 2011 at 03:59:06PM +0200, Shane Kerr wrote:
> > I'd love to, but I don't know if there's enough time for studying it. Maybe I'll
> > enjoy it when there'll be the need to optimise it ;-). So, for now, I just take
> > the description.
> In my mind the most important implementation thing is the use of radix
> trees, which are a lot faster once you have more than a smallish number
> of match items, since it is an O(1) match regardless of how many match
> items there are. (In the address part of ACL-matching only, not talking
> about TSIG of course; although TSIG-matching can probably be made O(1)
> by using a hash-table.)

Well, I thought the plan would be:
• The naïve approach first, which would be O(n), but would work.
• Introduce grouping/reordering of logic branches (which by itself could help a
  little, but would be needed for the next one).
• Implement compaction of IP checks, possibly TSIG checks in a subexpression of
  only the same kind of check (eg. if there's a huge part of the expression
  containing only IP checks, the whole part would be replaced by one radix
  check). I'd like to do this in logic-operator agnostic way, so we could add
  new operators without modifying this. This shouldn't be too complicated, I
  actually have an idea how to do it, but I haven't written it down yet.
• Think about what to do if they interleave or something (eg. huge OR having a
  check for both IP and TSIG in each subelement, it wouldn't be optimised by the
  above, but probably could be optimised somehow).

With regards

In the name of kernel, compiler and holy penguin

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20110530/7e249751/attachment.bin>

More information about the bind10-dev mailing list