[bind10-dev] ACL Syntax proposal

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


Hello

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