From owner-freebsd-net  Wed May 20 04:38:59 1998
Return-Path: <owner-freebsd-net@FreeBSD.ORG>
Received: (from majordom@localhost)
          by hub.freebsd.org (8.8.8/8.8.8) id EAA19478
          for freebsd-net-outgoing; Wed, 20 May 1998 04:38:59 -0700 (PDT)
          (envelope-from owner-freebsd-net@FreeBSD.ORG)
Received: from ns1.yes.no (ns1.yes.no [195.119.24.10])
          by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id EAA19458
          for <net@FreeBSD.ORG>; Wed, 20 May 1998 04:38:52 -0700 (PDT)
          (envelope-from eivind@bitbox.follo.net)
Received: from bitbox.follo.net (bitbox.follo.net [195.204.143.218])
	by ns1.yes.no (8.8.7/8.8.7) with ESMTP id LAA10684;
	Wed, 20 May 1998 11:38:44 GMT
Received: (from eivind@localhost)
	by bitbox.follo.net (8.8.8/8.8.6) id NAA05067;
	Wed, 20 May 1998 13:38:43 +0200 (MET DST)
Message-ID: <19980520133843.32113@follo.net>
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...
References: <Pine.BSF.3.95.980520002407.21215A-100000@current1.whistle.com> <199805200747.JAA11373@labinfo.iet.unipi.it>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Mailer: Mutt 0.89.1i
In-Reply-To: <199805200747.JAA11373@labinfo.iet.unipi.it>; from Luigi Rizzo on Wed, May 20, 1998 at 09:47:35AM +0200
Sender: owner-freebsd-net@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.org

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