Date: Wed, 20 May 1998 13:38:43 +0200 From: Eivind Eklund <eivind@yes.no> To: Luigi Rizzo <luigi@labinfo.iet.unipi.it>, Julian Elischer <julian@whistle.com> Cc: kjc@csl.sony.co.jp, net@FreeBSD.ORG Subject: Re: struct ifnet handling... Message-ID: <19980520133843.32113@follo.net> In-Reply-To: <199805200747.JAA11373@labinfo.iet.unipi.it>; from Luigi Rizzo on Wed, May 20, 1998 at 09:47:35AM %2B0200 References: <Pine.BSF.3.95.980520002407.21215A-100000@current1.whistle.com> <199805200747.JAA11373@labinfo.iet.unipi.it>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, May 20, 1998 at 09:47:35AM +0200, Luigi Rizzo wrote: > > > where there were logical splits, based on an automated transform of > > > rules. These differences _are_ there, no matter what - there are > > > those 6 classes of rules (at least). > > > > > > BTW: The concept of 'chains' are used on the Ciscos (there called > > > 'rule lists' IIRC). > > > > what's so difficult about: > > > 100 [common rules always done] > > <snip> > > Nothing :) It screws the optimizing pass (not running the rules an optimizer has generated, just the cost of the actual optimization pass). A simple optimizer for rulesets is O(N^2 * 2^M) for the first pass, where N is the number of rules in a chain, and M is the number of splits (skipto-rules). The bound will be quite a bit better for the average case, but each split still double the work for the later rules in the chain (though increase in work doesn't always carry over, so you won't necessarily end up with an exponential timebound). The bound O(N^2 * 2^M) makes me want to reduce the length of the chains, which can easily be done by finding their natural organization through a pre-processing pass. Remember: I'm talking mostly of internal kernel organization here - I'm not talking about how the user should manipulate or see the rules. It might be convenient for the user to work in terms of chains, too, but that is a side-issue. > I think it is only a matter of naming (witnessed by the "rule list" > name used by cisco) and perhaps of having some default demux/mux of > 'chains' (but that could give a loss of flexibility for no real > performance advantage). I still don't see how you're loosing flexibility, even if you should decide to provide this interface as an alternate interface for the users. Eivind. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19980520133843.32113>