From: Michael Bellion <mbellion@hipac.org>
To: Emmanuel Fleury <fleury@cs.aau.dk>
Subject: Re: [ANNOUNCE] Release of nf-HiPAC 0.9.0
Date: Mon, 26 Sep 2005 18:03:27 +0200
User-Agent: KMail/1.8.1
Cc: linux-kernel@vger.kernel.org, netdev@oss.sgi.com
References: <200509260445.46740.mbellion@hipac.org> <200509261638.12731.mbellion@hipac.org> <43380E4A.1060604@cs.aau.dk>
In-Reply-To: <43380E4A.1060604@cs.aau.dk>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200509261803.28150.mbellion@hipac.org>
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2838
Lines: 63

Hi,

> > But your performance tests have a serious flaw:
> > You construct your rule set by creating one rule for each entry in your
> > packet header trace. This results in an completely artificial rule set
> > that creates a lot of redundancy in the nf-HiPAC lookup data structure
> > making it much larger than the Compact Filter data structure.
>
> Yes, it was intended to be a worst case for our scheme (not realistic
> but worst case)..

Sorry, but this is far away from the worst case for your scheme. Actually it 
is a quite good case for your compiler, because every rule is fully specified 
(meaning there are no wildcards in any rule) and there are no ranges or masks 
involved. 
Try using a mixed rule set that contains rules that only specify certain 
dimensions and have wildcards on the other dimensions. Try using rules with 
ranges and masks.
Try using overlapping rules, meaning rules that completely or partly overlap 
other rules in certain dimensions.
This will make your data structure grow!

> > I am currently working on a new improved version of the algorithm used in
> > nf-HiPAC. The new algorithmic core will reduce memory usage while at the
> > same time improving the running time of insert and delete operations. The
> > lookup performance will be improved too, especially for bigger rulesets.
> > The concepts and the design are already developed, but the implementation
> > is still in its early stages.
> >
> > The new algorithmic core will make sure that the lookup data structure in
> > the kernel is always fully optimized while at the same time allowing very
> > fast dynamic updates.
> >
> > At that point Compact Filter will not be able to win in any performance
> > test against  nf-HiPAC anymore, simply because there is no way to
> > optimize the lookup data structure any further.
>
> Well, you already said this last time we had exchanged some mails
> (it was more than one year ago if I count well).

Yes, you are right. The HiPAC project has gone through some tough times over 
the last 2 years. With MARA Systems the HiPAC Project has finally found a 
strong partner that is fully committed to the concept of Open Source 
Software. This allows me to continue the development of HiPAC under the GNU 
GPL license.

> Anyway, I doubt you can get something that you can update dynamically
> AND small in size following your way of doing. But, prove me wrong and
> I'll be happy. :)

Ok, I'll do that :)

Regards,
    +---------------------------+
    |      Michael Bellion      |
    |   <mbellion@hipac.org>    |
    +---------------------------+

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/