Subject: Re: ipfilter performance with 'count' rules on NetBSD-1.4/i386
To: Erik Rungi <blackbox@openface.ca>
From: Jefferson Ogata <jogata@nodc.noaa.gov>
List: current-users
Date: 09/14/1999 17:16:36
If you assign a weight to each IP address based on the expected utilization, you
can build an optimized tree along the lines of a Huffman-coding tree that should
get you what you really want.

Yes, the configuration file will be ugly, so come up with a nice metalanguage
and write a Perl script to generate the IPFilter rules. It'll be fun! Maybe
Darren would include it in the IPFilter tools.

Erik Rungi wrote:
> 
> On Tue, 14 Sep 1999, David Maxwell wrote:
> 
> > Additionally, you specifically stated that you didn't use 'quick' in
> > any of the rules. Would you mind running the test with quick on all
> > the rules? Depending on the distibution of destination, it should cut
> > the workload in half. If the addresses for your rules don't overlap,
> > you could then optimize the most used rules to the top of the list.
> 
> In the case of optimization, you have to keep track of hits, but I'm sure it
> could be done.  It would would be nice if the kernel could do this.
> 
> > If you have rules that do overlap subnets, you could generate the
> > total by adding the smaller networks at 'stats' time. (Assuming you
> > aren't collecting for a portion of a subnet, and the whole net,
> > but not another portion - if so, change the whole subnet one to collect
> > the other portion with a quick rule, and sum the counts later.)
> 
> In my case I'm adding up individual IPs.  With this case it has also been
> suggested that I break the rules down using the HEAD/GROUP keywords which
> could bring the processing time down by a factor of LOG(N) in theory.  In this
> case, optimization wouldn't really work (same time to get to the bottom of the
> tree in any case).  But the configuration file would be soooo ugly.
> 
> In either case the configuration of IPF becomes considerably more complex in
> my opinion.
> 
> Erik

-- 
Jefferson Ogata <jogata@nodc.noaa.gov> National Oceanographic Data Center
You can't step into the same river twice. -- Herakleitos