[ANNOUNCE] Release of nf-HiPAC 0.9.0

[ANNOUNCE] Release of nf-HiPAC 0.9.0

[Michael Bellion]

Hi

I am happy to announce the release of nf-HiPAC version 0.9.0

During the development of version 0.9.0 everything was ported to Linux kernel 
2.6 and large parts of the kernel code have been rewritten.
The kernel patch is now fairly non-intrusive: it only adds one simple function 
to ip_tables.c. The rest of the patch introduces new files to the kernel. 
The new release fixes all known bugs and also introduces some new features.

Since the last release I have become part of MARA Systems AB 
( http://www.marasystems.com ). MARA Systems AB is now the commercial backer 
of the HiPAC Project and finances it completely. Together MARA Systems and I 
will make sure that HiPAC is actively maintained and further developed under 
the GNU GPL.


For all of you who don't know nf-HiPAC yet, here is a short overview:

nf-HiPAC is a full featured packet filter for Linux which demonstrates the
power and flexibility of HiPAC. HiPAC is a novel framework for packet
classification which uses an advanced algorithm to reduce the number of
memory lookups per packet. It is ideal for environments involving large rule
sets and/or high bandwidth networks.

nf-HiPAC provides the same rich feature set as iptables, the popular Linux
packet filter. The complexity of the sophisticated HiPAC packet
classification algorithm is hidden behind an iptables compatible user
interface which renders nf-HiPAC a drop-in replacement for iptables. Thereby,
the iptables' semantics of the rules is preserved, i.e. you can construct your
rules like you are used to. From a user's point of view there is no need to
understand anything about the HiPAC algorithm.

The nf-hipac user space tool is designed to be as compatible as possible to
'iptables -t filter'. It even supports the full power of iptables targets,
matches and stateful packet filtering (connection tracking) besides the native
nf-HiPAC matches. This makes a switch from iptables to nf-HiPAC very easy.
Usually it is sufficient to replace the calls to iptables with calls to
nf-hipac for your filter rules.

Why another packet filter?
Performance:
    iptables, like most packet filters, uses a simple packet classification
    algorithm which traverses the rules in a chain linearly per packet until a
    matching rule is found (or not). Clearly, this approach lacks efficiency.
    As networks grow more and more complex and offer a wider bandwidth linear
    packet filtering is no longer an option if many rules have to be matched
    per packet. Higher bandwidth means more packets per second which leads to
    shorter process times per packet. nf-HiPAC outperforms iptables regardless
    of the number of rules, i.e. the HiPAC classification engine does not
    impose any overhead even for very small rule sets.

Scalability to large rule sets:
    The performance of nf-HiPAC is nearly independent of the number of rules.
    nf-HiPAC with thousands of rules still outperforms iptables with 20 rules.

Dynamic rule sets:
    nf-HiPAC offers fast dynamic rules et updates without stalling packet
    classification in contrast to iptables which yields bad update performance
    along with stalled packet processing during updates.

More information about the project can be found at:    http://www.hipac.org
The releases are published on:    http://sourceforge.net/projects/nf-hipac/

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

Re: [ANNOUNCE] Release of nf-HiPAC 0.9.0

[Amin Azez]

This auto-factorization of rules seems cool.

> Dynamic rule sets:
> nf-HiPAC offers fast dynamic rules et updates without stalling packet
>classification in contrast to iptables which yields bad update performance
> along with stalled packet processing during updates.

Does it also remove the "upload rules in bulk" issue of iptables and
make use of links lists (or trees) to upload small changes singly? I
recall someone released a re-write a while ago that took care of this,
but this seems to do rule-factoring too to reduce the number of check
operations.

Speaking under fear of blasphemy I'm wondering what stops this becoming
iptables proper? (ipv4 anyway)?  OK, it would want linking to
nf_conntrack instead of ip_conntrack and a v6 version doing type stuff,
but it seems the biz.

Azez

Re: [ANNOUNCE] Release of nf-HiPAC 0.9.0

[Henrik Nordstrom]

On Wed, 28 Sep 2005, Amin Azez wrote:

> Does it also remove the "upload rules in bulk" issue of iptables and
> make use of links lists (or trees) to upload small changes singly?

Yes. nf-HiPAC uses netlink messages for rule updates, carrying just the 
updates. It does not exchange complete rulesets on each update like 
iptables does.

> I recall someone released a re-write a while ago that took care of this, 
> but this seems to do rule-factoring too to reduce the number of check 
> operations.

iptables per definition must always send a whole new iptable (compiled 
ruleset) to the kernel as one big blob as it is the userspace who 
constructs the iptable and the kernel has no knowledge (or capability) to 
modify an iptable inplace, only replace it with another submitted by 
userspace.

As nf-HiPAC is using another internal representation of the rules it does 
not need this, and the updates carry only the rules you are updating.

> Speaking under fear of blasphemy I'm wondering what stops this becoming
> iptables proper?

Not much. It is already very near a full replacement of iptables filter 
table. It does not yet have support for the other table types but it's 
trivial to add. The nat table has to wait for the completetion of the 
restructuring of the nat code currently taking place however, but after 
2.6.14 this should not be a problem to implement from what I have 
understood. The problem currently is that the nat core nat is very tightly 
coupled with iptable_nat, but this is being addressed already by the 
Netfilter team.

> OK, it would want linking to nf_conntrack instead of ip_conntrack

This should be trivial. The optional conntrack dependency is already well 
isolated in a separate very small module. Some of this isolated code 
obviously needs to be changed when using nf_conntrack but not much.

> and a v6 version doing type stuff, but it seems the biz.

IPv6 requires a bit more work due to the larger key size in 
source/destination addresses. HiPAC currently only implements up to 32-bit 
lookup dimensions (source/destination/protocol/ports etc..).

Regards
Henrik

Re: [ANNOUNCE] Release of nf-HiPAC 0.9.0

[Bart De Schuymer]

Op wo, 28-09-2005 te 15:05 +0100, schreef Amin Azez:
> This auto-factorization of rules seems cool.
> 
> > Dynamic rule sets:
> > nf-HiPAC offers fast dynamic rules et updates without stalling packet
> >classification in contrast to iptables which yields bad update performance
> > along with stalled packet processing during updates.
> 
> Does it also remove the "upload rules in bulk" issue of iptables and
> make use of links lists (or trees) to upload small changes singly? I
> recall someone released a re-write a while ago that took care of this,
> but this seems to do rule-factoring too to reduce the number of check
> operations.
> 
> Speaking under fear of blasphemy I'm wondering what stops this becoming
> iptables proper? (ipv4 anyway)?  OK, it would want linking to
> nf_conntrack instead of ip_conntrack and a v6 version doing type stuff,
> but it seems the biz.

http://www.hipac.org/documentation/user_guide.html states some
incompatibilities with iptables.

What's always resisted me from looking to it closely is that there is no
documentation about the implementation. I'm especially interested in how
the code deals with matches. The reason why counters aren't supported
interests me too, I can't see why adding 1 to a 64-bit integer would
result in a noticeable performance drop.
Also, is it not possible to make a B+ tree with the standard iptables? I
don't see why it shouldn't be possible. The jump to a new chain can be
seen as going deeper into the B+ tree. So it should be possible to
construct an iptables table structure that looks very similar to the B+
tree of nf-hipac, for some given rule set. I guess this will be somewhat
slower than nf-hipac, but I'd like to see the performance difference...

cheers,
Bart

Re: [ANNOUNCE] Release of nf-HiPAC 0.9.0

[Michael Bellion]

[-- Attachment #1: Type: text/plain, Size: 2783 bytes --]

Hi

> > Speaking under fear of blasphemy I'm wondering what stops this becoming
> > iptables proper? (ipv4 anyway)?  OK, it would want linking to
> > nf_conntrack instead of ip_conntrack and a v6 version doing type stuff,
> > but it seems the biz.
>
> http://www.hipac.org/documentation/user_guide.html states some
> incompatibilities with iptables.

Yes, currently there are some negligible differences. Most of them can be 
worked around easily and will be fixed in future versions.

> What's always resisted me from looking to it closely is that there is no
> documentation about the implementation. 

Yes, that is true and a big problem.
There are a lot of people that think that nf-HIPAC would rearrange the rules 
in some user-defined chains. But that is completely wrong. Nf-HiPAC used a 
completely different approach. The rules are translated into a very efficient 
data structure that does not have anything to do with iptables' 
representation of rules in tables and chains.
I really need to add some documention about the algorithmic approach. 

> The reason why counters aren't supported
> interests me too, I can't see why adding 1 to a 64-bit integer would
> result in a noticeable performance drop.

It does make a difference, because it means a write to an otherwise completely 
read-only ruleset. 
But independent from that, the netfilter developers agree that it is a bad 
approach to have counters enabled by default for each and every rule 
(refering to last years netfilter workshop). Future versions of iptables (or 
successors of iptables) won't come with counters enabled by default on all 
rules.

It is very easy to add support for counters to nf-HiPAC. Just write an 
iptables match or target for it.

> Also, is it not possible to make a B+ tree with the standard iptables? I
> don't see why it shouldn't be possible. The jump to a new chain can be
> seen as going deeper into the B+ tree. So it should be possible to
> construct an iptables table structure that looks very similar to the B+
> tree of nf-hipac, for some given rule set. I guess this will be somewhat
> slower than nf-hipac, but I'd like to see the performance difference...

Sorry, but you seem to confuse some things.
nf-HiPAC is not based on B+trees or any other kind of B-trees. 
nf-HiPAC does not rearrange the rules in some custom userdefined chains in 
order to achieve better performance.
Instead nf-HiPAC translates the iptables representation of tables and chains 
into a completely different data structure that is much more efficient.

And, trust me, the lookup data structure used in nf-HiPAC will be much faster 
than anything you can construct based on iptables and user-defined chains.

Regards
	Michael Bellion


[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [ANNOUNCE] Release of nf-HiPAC 0.9.0

[Bart De Schuymer]

Op zo, 02-10-2005 te 14:30 +0200, schreef Michael Bellion:
> > Also, is it not possible to make a B+ tree with the standard iptables? I
> > don't see why it shouldn't be possible. The jump to a new chain can be
> > seen as going deeper into the B+ tree. So it should be possible to
> > construct an iptables table structure that looks very similar to the B+
> > tree of nf-hipac, for some given rule set. I guess this will be somewhat
> > slower than nf-hipac, but I'd like to see the performance difference...
> 
> Sorry, but you seem to confuse some things.
> nf-HiPAC is not based on B+trees or any other kind of B-trees. 

So the algorithm of nf-hipac was changed in view of the one you were
using in 2003? I remembered from your talk then that you used B+trees
and this is confirmed by the slides you've finally put online.

cheers,
Bart

Re: [ANNOUNCE] Release of nf-HiPAC 0.9.0

[Michael Bellion]

[-- Attachment #1: Type: text/plain, Size: 1586 bytes --]

Hi

> Op zo, 02-10-2005 te 14:30 +0200, schreef Michael Bellion:
> > > Also, is it not possible to make a B+ tree with the standard iptables?
> > > I don't see why it shouldn't be possible. The jump to a new chain can
> > > be seen as going deeper into the B+ tree. So it should be possible to
> > > construct an iptables table structure that looks very similar to the B+
> > > tree of nf-hipac, for some given rule set. I guess this will be
> > > somewhat slower than nf-hipac, but I'd like to see the performance
> > > difference...
> >
> > Sorry, but you seem to confuse some things.
> > nf-HiPAC is not based on B+trees or any other kind of B-trees.
>
> So the algorithm of nf-hipac was changed in view of the one you were
> using in 2003? I remembered from your talk then that you used B+trees
> and this is confirmed by the slides you've finally put online.

The reason why I said that b-trees are not used in hipac was that the b-trees 
are not the main data structure and are not the main solution of the problem.

The problem is solved by a graph that consists of a lot of nodes.

During a lookup this graph is traversed and each node that is visited 
internally uses again a certain data structure. In 2003 btrees were used 
internally at each node of the graph. In the current implementation simple 
static binary search is used instead.

So basically you can forget about the btrees. They are not important for the 
solution of the problem. Have a closer look at the slides of the more recent 
presentations.

Best regards
	Michael Bellion

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]